If $n \in \mathbb{N} - \{1\}$, $ a \in \mathbb{Z}$, and $gcd(a,n)=1$, show there is $1 \leq i<n$ with $n|(a^i -1)$.
So far I have shown that, if $gcd(a,n)=1$, then $gcd(a^j,n)=1$. I also have a theorem that states that, given the conditions in the problem, there exists $r \in \mathbb{N}$ with $1 \leq r < n$ and $(r,n)=1$ so that $n|(ar-1)$. I'm thinking I can show $r=a^{i-1}$ so that $n|(a^i-1)$.
As $(a,n)=1, a^i\pmod n$ will lie in $[1,n-1]$
Now if all the remainders are distinct, using Pigeonhole Principle exactly one $a^i\equiv1\pmod n$
Else let $a^r\equiv a^s\pmod n, n-1\ge r>s\ge1\iff n|a^{r-s}(a^s-1)\implies n|(a^s-1)$ as $(a,n)=1$