How to solve this congruence?

Question

Given that $6^{12} ≡ 16\pmod {109}$. Is there a $k$ such that $16^k ≡ 6 \pmod {109}$? If there is, then find all the $k$'s.

Does anyone know how to do this?

Thanks

Answer 1

Hint:

• $109$ is prime;
• if $16^k\equiv6\pmod{109}$ then $6^{12k-1}\equiv1\pmod{109}$;
• but you also know $6^{108}\equiv1\pmod{109}$;
• obtain a contradiction from the last two points.

Answer 2

This is a hard question, I can give an answer relying on the fact that $6$ has order $108$ mod $109$. So then we have the elements $6,6^2,6^3\dots 6^{168}\equiv1 \bmod 109$ are all different. the powers of $16$ are precisely $6^{12},6^{24},6^{36}\dots 6^{168}$ and no more, since they cycle (this is because $12$ divides $108$ which is the order of $6\bmod 108$, however you need to know the order of this beforehand).

In general if you want for an integer $k$ to exist so that $(n^a)^k \equiv n \bmod m$ this happens if and only if $a$ and the order of $n$ mod $m$ are relatively prime.

---

I just noticed we can find a shortcut in this particular case. Notice $108$ is $2^2\cdot 3^2$. Now, notice the order of $6$ mod $109$ needs to be a nontrivial divisor of $108$ by Lagrange's theorem in group theory, this number cannot be relatively prime to $12$ because of the prime decompositon of $108$, so you don't actually have to calculate the order of $6$ to know, although this only works because $12$ contains all of the prime divisors of $108$ in its prime factorization.