1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! Why is the 2 a primitive root exactly? Your last line says the conversion is always allowed, so why is this relevant? $\endgroup$ – Schiavini Oct 16 '15 at 15:18
  • $\begingroup$ 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) $\endgroup$ – André Nicolas Oct 16 '15 at 15:28
  • $\begingroup$ (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$. $\endgroup$ – André Nicolas Oct 16 '15 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.