If $\gcd(a,N)=1$, why is it that the base $a$ will produce at least one instance of a power equal to $1\pmod N$?

Question

I'm familiar with Fermat's Little Theorem and Euler's Totient, but I'm wondering whether the fact that the only shared factor of $(a,N)=1$ has something to do with the fact that, given the prior constraints there exists at least one $x$ (with $x$ being one of elements of the least non-zero positive remainder class of $N$) where $a^x \equiv 1 \pmod{N}$?

It doesn't appear to be dependent upon the modulus being prime since using a modulus of 10 the following is true:

$9^1\pod{10}=9$
$9^2\pod{10}=1$
$9^3\pod{10}=9$
$9^4\pod{10}=1$
$9^5\pod{10}=9$
$9^6\pod{10}=1$
$9^7\pod{10}=9$
$9^8\pod{10}=1$
$9^9\pod{10}=9$

This is also really naive but another observation is that given the previous assumptions the initial base will always be less than $N$ and $a^1 \pmod{N}$ will always return $a$, so given $\gcd(a,N)=1$, $a$ will always produce at least one remainder other than $1$.

I know there's some intuition that I'm missing?

Answer 1

Consider all powers $a^r\bmod N$ for $r=1,2,3,\ldots$ There are an infinite number of them, but they can only take values $0\le a^r\bmod N\le N-1$. So sooner or later we must encounter a repeated value; say $a^s\equiv a^t\bmod N$, for some $s<t$.

Now, since $\gcd(a,N)=1$, we know that $\gcd(a^s,N)=1$. So we can divide by $a^s$, and we get $1\equiv a^{t-s}\bmod N$. Which is what we wanted.

Answer 2

It is because for a number to have an inverse (i.e. some element which product of both is a residue of $1$), we need the number to be relatively prime with the modulus.

$$a \cdot a^{x -1} \equiv_N 1$$

We have an inverse of $a$ in this case. You see now?

§ Further Explanation §

$$ax + Ny = 1$$

So $x$ modulo $n$ is the inverse but by Bezout's theorem this is only true if $a$ and $N$ are relatively prime.

Answer 3

Not sure this fully answers you question (not very clear to me), but $\gcd(a,N)=1$ implies $a$ is a unit modulo $N$, so the congruence class of $a\bmod N$ generates a finite group, and it has a power congruent to $1$. One may add that this group is a subgroup of the (multiplicative) group $U_N$ of units modulo $N$, and by Lagrange's theorem, it has order a divisor of $$|U_N|=\varphi(N).$$ For your example, $\;\varphi(10)=\varphi(2)\,\varphi(5)=4$.