Why is it that exponents that are divisors of φ(N) capable of generating the identity element as a power when N is prime?

Question

Let $p=x$ where $a^x \equiv 1\pmod N$. When $N$ is prime I can check whether $p=N-1$ and if it is, there are a full set of remainders. However, if $p<N-1$, I need to keep checking. For example, if $N=11$ and $a=3$ the following powers are generated:

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

$3^{10} \pmod {11}$ doesn't represent the smallest exponent where $a^x \equiv 1\pmod N$ because equivalent powers exist (e.g. $3^6 \equiv 3^1 \pmod {11}$. The least positive exponent where $a^x \equiv 1\pmod N$ is $5$. So $p<N-1$. What I'm trying to figure out is why only divisors of $φ(N)$ are capable of $a^x \equiv 1\pmod N$, why can't $7$ be a possible exponent that returns $1$?

Answer 1

Let $(a,m)=1$. Then the smallest natural number $h$ such that $a^h\equiv1\mod m$ is called the order of $a\mod m$, denoted as $O(a)\mod m$. It can be shown that$$h'\in\Bbb N:a^{h'}\equiv1\mod m\implies h|h'$$where $h$ is $O(a)\mod m$. This is because $h'=qh+r,0\le r<h\implies a^{h'}=a^{qh+r}\equiv a^r\equiv1\mod m$.

If $r\ne0$, we would have found an integer $r$ less than $h$ such that $a^r\equiv1\mod m$. But this is not possible, since $h$ is the minimum such natural. Thus, $r=0$.

In addition to this, it is easy to see that any multiple of $h=O(a)\mod m$ will be congruent to $1\mod m$.

Now you may recall from Fermat's Little Theorem that for prime $p$ and $a$ coprime with it, $a^{p-1}=a^{\varphi(p)}\equiv1\mod p$. Thus, $O(a)\mod p$ must divide $\varphi(p)$.

From this discussion, it is apparent that

• Not all divisors $x$ of $\varphi(p)=p-1$ satisfy $a^x\equiv1\mod p$. For example, $p=5,a=2,x=2$.

• The $O(a)\mod p$ is one of the factors of $\varphi(p)=p-1$.

• A natural number $x$ satisfies $a^x\equiv1\mod p$ iff $x$ is a positive multiple of $O(a)\mod p$.

Answer 2

Let $N$ be a prime (as you specify) and let $(a,N) = 1$.

Let $\omega$ be the smallest positive integer such that

$$ a^{\omega} \equiv 1 \pmod{N}.$$

Then $\omega$ is called the order of $a$ mod $N$.

Since $\omega | \phi(N)$, it follows that $\phi(N) = k\omega$, for some positive integer $k$. Hence,

$$a^{\phi(N)} \equiv a^{k\omega} \equiv (a^{\omega})^{k}\equiv (1)^{k}\equiv 1 \pmod{N}.$$

In fact, we see that by taking any integer $s \in \lbrace 1, 2, \ldots, k \rbrace$, then

$$ a^{s\omega} \equiv (a^{\omega})^{s} \equiv (1)^{s} \equiv 1 \pmod{N}.$$

And so, we obtain a congruence equivalent to $1$ whenever the exponent is a multiple of the order of $a$ modulo $N$ (or equivalently, when the exponent divides the value of Euler's $\phi$-function).

Remark: There is no need to require that $N$ be prime; the above holds for composite $N$ as well.