# Converting $2^{16x} \equiv 2^6\text{ (mod 19)}$ to $16x\equiv 6\text{ (mod 18)}$

In my number theory book, I see the congruence $2^{16x} \equiv 2^6\text{ (mod 19)}$ being converted to $16x\equiv 6\text{ (mod 18)}$.

My question is: Why is this allowed and what are the general rules for this conversion?

ps: $16x\equiv 6\text{ (mod 18)}$ is later solved as $x\equiv 6\text{ (mod 9)}$, but that's not an issue.

Note that $2$ is a primitive root of $19$, that is, $2$ has order $18$ modulo $19$.
In general, let $p$ be prime, and suppose that $g$ is a primtive root of $p$. Then $g^i\equiv g^j\pmod{p}$, where $j\gt i$, if and only if $g^{j-i}\equiv 1\pmod{p}$. And $g^{j-i}\equiv 1\pmod{p}$ if and only if the order of $g$ modulo $p$, namely $p-1$, divides $j-i$.
So $g^j\equiv g^i\pmod{p}$ if and only if $j\equiv i\pmod{p-1}$.
• You are welcome. In general it is unpleasant to verify that $a$ is a primitive root of $p$. For $2$ and $19$, we could do it the hard way. Compute $2^i$ modulo $19$, and check that the smallest positive $i$ for which $2^i\equiv 1\pmod{19}$ is $18$. But there are shortcuts. If the order of $a$ is not $p-1$, then $a^{(p-1)/q}\equiv 1\pmod{p}$ for some prime divisor $q$ of $p-1$. So all we need to do in our case is to check that $2^6\not\equiv 1\pmod{19}$, and that $2^{9}\not\equiv 1\pmod{19}$. (more) – André Nicolas Oct 16 '15 at 15:28
• (more) The first one is a computation, $2^6\not\equiv 1\pmod{19}$. The second one also, although if we know something about quadratic residues, the fact that $2^9\ot\equiv 1\pmod{19}$ follows from the fact that $2$ is a quadratic non-residue of $19$. – André Nicolas Oct 16 '15 at 15:30