0

I'm trying to prove intuitively that there exists a number $k$ such that

$$a^k \equiv 1 (m),$$

iff $a$ and $m$ are coprime.

One of the ways of the proof is easy: If $a^k \equiv 1 (m)$, then that means $a^k = pm+1$ for some integer $p$. Since all consecutive numbers are coprime, then $a^k$ and $pm$ are coprime, which directly implies that $a$ and $m$ are also coprime.

However, I don't know how to prove the other direction of the statement, that is, if $a$ and $m$ are coprime, then there exists a number $k$ such that $a^k \equiv 1 (m)$, without invoking permutation properties of the reduced residue system modulo $m$ as shown in here.

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
elcocodrilotito
  • 77
  • 5
  • Euler's theorem establishes even a concrete solution. The pigeonhole principle allows to easily prove the existence : Since there must be powers with equal residue , we can divide by a suitable power to get the desired result because $a$ must be invertible mod $m$ – Peter Feb 10 '23 at 15:20
  • 1
    The permutation-based view is the most intuitive way to view this. You may find it more intuitive viewed graphically in terms of orbits, e,g, see the argument [here](https://math.stackexchange.com/a/3850292/242), generalized to recurrences in any finite ring. – Bill Dubuque Feb 10 '23 at 16:05
  • 1
    Those who fail to master these simple ubiquitous facts about such periodicity often end up (painfully) [reinventing the wheel (cycle).](https://math.stackexchange.com/search?tab=votes&q=user%3a242%20wheel%20cycle) – Bill Dubuque Feb 10 '23 at 16:09

0 Answers0