Inverse $2^{18}$ in GF(23) without extended euclidean algorithm

Question

I have a little question about the calculation of the inverse of $2^{18} \mod\ 23$. I have the solution of this:

$$ \text{The inverse of $2^{18}$ is $2^{-18}$. The modulus in the exponent is $\Phi(23)=22$.}\\ 2^{-18} = 2^{-18+22} = 2^4 = 16 \ mod \ 23 $$

Thats, of course, the right solution for GF(23), but I do not know why I can calculate the inverse like this. I tried it with the Euler-Theorem:

$$ a^{-1} = a^{\phi(23)-1} \rightarrow 2^{18*(22-1)} = 2^{18*21} = 16 \ mod \ 23 $$

That leads to the same result, but is much more complicated when one is not allowed to use a calculator. So I'm interested in the idea behind the 1. solution.

Meiner

Answer 1

Another way of looking at the first way of doing things is that little Fermat (or Euler, which you quote) tells us that, modulo $23$, we have $2^{22}\equiv 1$. Rewrite this as $2^{18}\cdot 2^4\equiv 1$ and you have the first argument (albeit in a slightly different form).

Answer 2

Since $23$ is prime, $2^{23 - 1} = 1 \mod 23$ by Fermat. Thus $2^4 = 16$ is the inverse.

Answer 3

Here is a boring way of doing this,and way longer.Though I wanted to see could a equation with large power be solved that way. $$2^{18}x=1\pmod{23}\\2^{18}=-22\pmod{23}\pmod{23}\\2^{17}x=-11\pmod{23}\\2^{17}x=12\pmod{23}\\2^{15}x=3\pmod{23}\\2^{15}x=-20\pmod{23}\\2^{13}x=-5\pmod{23}\\2^{13}x=18\pmod{23}\\2^{12}x=9\pmod{23}\\2^{12}x=-14\pmod{23}\\2^{11}x=-7\pmod{23}\\2^{11}x=16\pmod{23}\\2^7x=1\pmod{23}\\2^7x=-22\pmod{23}\\2^6x=-11\pmod{23}\\2^6x=12\pmod{23}\\2^4x=3\pmod{23}\\2^4x=-20\pmod{23}\\2^2x=-5\pmod{23}\\2^2x=18\pmod{23}\\2x=9\pmod{23}\\2x=-14\pmod{23}\\x=-7\pmod{23}\\x=16\pmod{23}$$

Answer 4

Key Idea $\ $ If $\,\color{#c00}{2^n\equiv 1}\pmod{23}$ then exponents on $\,2\,$ may be considered $\color{#c00}{\pmod n}\ $ i.e.

$$\ \color{#0a0}{j\equiv k}\!\!\pmod n\ \Rightarrow\ 2^{\large\color{#0a0}j}\equiv 2^{\large\color{#0a0}k}\!\!\!\pmod{23}$$

Proof $\ \ j = k + ni\,\Rightarrow\,2^{\large j} = 2^{\large k+ni}= 2^{\large k} (\color{#c00}{2^{\large n}})^{\large i}\equiv 2^{\large k}\color{#c00}{(1)}^{\large i} \equiv 2^{\large k}\pmod{23}\ \ $ QED

Thus $ $ mod $\,23\!:\ \color{#c00}{ 2^{22}\equiv 1},\,$ and $\,\color{#0a0}{-18\equiv 4}\pmod{22}\,\Rightarrow\, 2^{\large\color{#0a0}{ -18}}\equiv 2^{\large\color{#0a0} 4}\equiv 16\pmod{23}$