1

Let $a$ and $n$ be natural numbers with $(a,n)=1$. Then there exists a natural number $k$ such that $a^k≡1 \pmod n$.

I am using Number Theory Through Inquiry which does not offer much in the way of help solving theorems. The previous theorems are meant to set up proofs for the ones that follow, but I can't quite get this one.

Derek Luna
  • 2,732
  • 8
  • 19
  • Looking at $a^1, a^2, .., a^{n+1}$ modulo $n$, they can't all be different, by the pigeonhole principle. So there must be some distinct $i,j$ (with, say, $j > i$) such that $a^i \equiv a^j \pmod{n}$. But then $a^{j-i} \equiv 1 \pmod{n}$, so we can choose $k = j-i$. Now a question for you, where did we use the fact that $(a,n) = 1$? – Woett Jul 04 '19 at 20:18
  • you were able to "divide out" the $a^i$ from the congruence – Derek Luna Jul 04 '19 at 20:22
  • Well spotted Derek! – Woett Jul 04 '19 at 20:23
  • Thanks for the help. – Derek Luna Jul 04 '19 at 20:26
  • Woett, there is a later problem that states the order is always less than $n$. Isn't your first comment strong enough to prove this list only up to $a^n$ and noticing that $(a,n)=1$ implies none of them can be $0$ either also prove this since there can only be $n-1$ of these and so two must be congruent and the same argument follows? – Derek Luna Jul 05 '19 at 02:08
  • Yes, you are completely correct :) To improve upon this further, note that if $(a,n) = 1$, then $(a^i, n) = 1$ as well for all $i \in \mathbb{N}$, by unique factorization. Using the notation that $\varphi(n)$ denotes the number of naturals smaller than $n$ that are relatively prime to $n$, this implies that $a^1, a^2, .., a^{\varphi(n)+1}$ cannot all be different mod $n$. This in turn then shows that $a^k \equiv 1 \pmod{n}$ for some $k \le \varphi(n)$. And in fact, a famous theorem by Euler states that $k = \varphi(n)$ works. Ie whenever $(a,n) = 1$, we have $a^{\varphi(n)} \equiv 1 \pmod{n}$. – Woett Jul 05 '19 at 22:40

0 Answers0