Proof: If $\text{gcd}(a,n)=1$ then $a^{\phi(n)}-1$ is divisible by $n$

Question

I was a bit surprised to see this question in an old abstract algebra test paper:

Prove that if $a$ and $n$ are two integers then such that $\text{gcd}(a,n)=1$ then $a^{\phi(n)}-1$ is divisible by $n$. Hence, show that the remainder is $5$ when $17^{72}+4$ is divided by $91$.

Firstly, I'm a bit confused by what $\phi(n)$ means in this context. Pretty sure it doesn't mean "any random function of $n$". Perhaps it refers to the Euler-phi function (?) Also, I'm not sure how the second statement follows from that. Any idea about what the question is trying to convey, and how to approach the problem?

Answer 1

This is no more than Euler theorem.

$\phi $ is Euler totient function which counts a number of natural numbers that are less than $n$ and relatively prime to $n$. This function is multiplicative so we have $$\phi (91) = \phi (13)\phi(7) = 12\cdot 6 = 72$$

So $$17^{72}+4 \equiv 1+4 = 5 \pmod {91}$$

so remainder when $17^{72}+4 $ is divided by $91$ is $5$

Answer 2

Note that $17^{72} \equiv 1 \pmod{91}$ Then $17^{72} + 4 \equiv 1 + 4 \equiv 5 \pmod{91}$

Since $91=7\cdot 13 \rightarrow \phi(91) = (7-1)(13-1)=72$

Then by Euler's Theorem: $17^{72} \equiv 17^0\equiv 1 \pmod {91}$

$\phi(n)$ stands for Euler Totient function: it counts the number of coprimes less than the modulus. In the case of a semiprime like $91$ is $(p-1)(q-1)$ and it is multiplicative $\phi(pq) = \phi(p)\phi(q)$

It is equivalent to $17^0$ since in the exponent domain computations are done $\mod \phi(n)$ then $72 \equiv 0 \pmod{72}$

Answer 3

An elementary proof of Euler's theorem (from group theory):

Consider $(\mathbb Z/n\mathbb Z)^*$ which is the group of invertibles from $\mathbb Z/n\mathbb Z$ for multiplication.

It is easy to see it is a group for multiplication.

$Class(a) \in (\mathbb Z/n\mathbb Z)^* \iff$ $a$ satisfies $\gcd(a,n) = 1$

(In all, we choose the representatives of the classes to be between $0$ and $n-1$ (the usual ones)).

Indeed, $Cl(a) \in (\mathbb Z/n\mathbb Z)^* \iff \exists \ Cl(b) \in \mathbb Z/n\mathbb Z$ such that $Cl(a)*Cl(b) = Cl(1)$ i.e. $Cl(ab) = Cl(1) \iff ab = 1 \mod n \iff \exists \ k\in \mathbb Z, \ ab = 1 +kn \ $ i.e. $ab - kn = 1 \iff \gcd(a,n) = 1$ (Bezout's theorem).

As a result, the order of $(\mathbb Z/n\mathbb Z)^*$ is $\phi(n)$.

Hence, by Lagrange's theorem, for all $Cl(a) \in (\mathbb Z/n\mathbb Z)^*, \ Cl(a)^{\phi(n)}=Cl(a^{\phi(n)}) = Cl(1)$ i.e. $a^{\phi(n)} = 1 \mod n$

Finally, for all $a$ such that $\gcd(a,n) = 1$, $a^{\phi(n)} = 1 \mod n$.