For the generalized form of FLT, assuming m and n are positive integers and p is prime, if $m \equiv n \pmod {p - 1}$ then for every $a$, $a^m \equiv a^n \pmod p$. Is the converse True, such that for every $a$, $a^m \equiv a^n \pmod p$ it must hold that $m \equiv n \pmod {p-1} $?
Asked
Active
Viewed 721 times
2 Answers
2
Yes. In fact, for any given prime $p$, you can find an integer $g$ with the property that $$g^m\equiv g^n\bmod p\implies m\equiv n\bmod (p-1);$$you don't have to require $a^m\equiv a^n\bmod p$ for every $a$ to guarantee that $m\equiv n\bmod (p-1)$. Such integers are known as primitive roots modulo $p$ (see Wikipedia).
Zev Chonoles
- 129,973
2
It is true. We use the fact that $p$ has a primitive root $g$. This is a number such that for any $a$ relatively prime to $p$, there is an integer $k$ such that $g^k\equiv a\pmod{p}$.
So $g$ has order $p-1$ modulo $p$: no positive power $g^k$ of $g$, with $1\le k\lt p-1$, is congruent to $1$ modulo $p$.
If $g^m\equiv g^n\pmod{p}$, where say $n\gt m$, then $g^{n-m}\equiv 1\pmod{p}$. It follows that the order of $g$ divides $n-m$, so $p-1$ divides $n-m$.
Remark: If $p$ is not a prime, the result fails. For example, let $p=8$. Then for any $a$, we have $a^4\equiv a^8\pmod{p}$, but $7$ does not divide $8-4$.
One can prove an analogue of the result for the numbers $2,4$ and $p^k$ and $2p^k$ where $p$ is an odd prime, but for no other numbers.
André Nicolas
- 507,029