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

Question

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.

Thanks in advance.

Answer 1

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}$.