I need to prove the following theorem for my Number Theory class,
Let $a$ and $n$ be natural numbers with $gcd(a,n)=1$. Then there exists a natural number $k$ such that $a^k\equiv 1 (mod \space n)$
I'm immensely awful at proofing so I have absolutely no idea how to prove this theorem. I haven't learned Fermat's Little Theorem yet so I can't use it in the proof either (if it's even applicable). But I do know how we define a residue systems modulo $n$, if that's useful. Could I please receive some guidance?
Best Answer
Take $n$ numbers $a^1,...,a^n$.
Because $\gcd(a,n)=1$ then $a^i \not \equiv 0 \pmod n $ for all $i=1,...,n$. Hence there are $n-1$ possible values from $1$ to $n-1$ for $n$ numbers $a^1,...,a^n$. According to the Pigeonhole principle, there exists $i,j \in \{1,...,n\}$ such that $i \ne j$ and $$a^j \equiv a^i \pmod n\implies a^i(a^{j-i}-1) \equiv0 \pmod n \implies a^{j-i} \equiv 1 \pmod n$$
Let's take $k = j-i$, then $a^{k} \equiv 1 \pmod n$