How to solve this congruence? 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
 A: 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.

A: 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.
