$a^{\phi(p)} \equiv 1 \pmod{p}$ if $a$ and $p$ are relatively prime.

Question

Why is it if we use 1 2 3 4 mod 5 and we take x^3 of these numbers, we come to: 1 3 2 4 (all numbers are different as you can see)? Why are they all different. Thanks

Explanation: $a^{\phi(p)} \equiv 1 \pmod{p}$ if $a$ and $p$ are relatively prime. You know that $\phi(5) = 5 - 1 = 4$, so if the exponent - say $k$ - is relatively prime to $4$, then the values of $x^k$ for $x \in {1, 2, 3, 4}$ will be all different. How can we conclude from $a^{\phi(p)} \equiv 1 \pmod{p}$ that all numbers are different?

Answer 1

We have by Euler's theorem that $a^{\phi(p)}\equiv1\pmod p$ if $(a,p)=1$,

so, if $bc\equiv1\bmod\phi(p)$, then $(a^b)^c=a^{bc}\equiv a^1=a\pmod p$,

so the map $a\mapsto a^b$ is invertible ($a\mapsto a^c)$ and therefore bijective.

For your particular example, take $p=5$, $\phi(p)=4$, $b=3$, and $c=3$.

Then the map $a\mapsto a^3$, which takes $1\mapsto1, 2\mapsto3, 3\mapsto2, $ and $4\mapsto4$ is its own inverse:

$$1\mapsto1\mapsto1, 2\mapsto3\mapsto2, 3\mapsto2\mapsto3, \text{ and } 4\mapsto4\mapsto4.$$

If the map were not one-to-one, it could not be inverted.

Answer 2

A simple explanation with Lagrange's theorem:

You have to show the map $x\mapsto x^3$ is injective in the multiplicative group $(\mathbf Z/5\mathbf Z)^\times$. As it is a group homomorphism because the group is commutative, it amounts to showing its kernel is $\{1\}$.

Consider $x\in\{1,2,3,4\}$ such that $x^3=1$. This implies the order of $x$ is a divisor of $3$. But as it is an element of the group $(\mathbf Z/5\mathbf Z)^\times$, of order $4$, it is also, by Lagrange, a divisor of $4$, and $\gcd(3,4)=1$. Therefore, necessarily, we have $x=1$.

Some details:

Denote, for any $x\in(\mathbf Z/5\mathbf Z)^\times$, $o(x)$ (the order of $x$) the least positive integer $k$ such that $x^k\equiv 1\mod 5$. It is easy to show that if $x^\ell\equiv 1\mod 5$, then $\ell$ is a multiple of $o(x)$.

Now suppose $x^3\equiv y^3\mod 5$. If we denote $y^{-1}$ the inverse of $y\bmod 5$, this implies that $x^3(y^3)^{-1}=\bigl(xy^{-1}\bigr)^3\equiv 1\mod 5$. By the property mentioned in the above §, $3$ is a multiple of $o(xy^{-1})$. Since $3$ is prime, this order is therefore either $1$ or $3$.

However, one can show that this order is also a divisor or $\#(\mathbf Z/5\mathbf Z)^\times$, which is $4$. As $3\not\mid 4$, the only solution is $\;o(xy^{-1})=1$, which means, by definition, that $xy^{-1}=1$, whence, multiplying both sides by $y$, $x=y$.

Answer 3

There are a few explanations:

• multiplicative inverses ( modular equivalent to reciprocal (division of 1 by a number)) are unique when defined.

• $a^n=-(-a)^n$ when $n$ is odd. as congruence is a weakened version of equality, it follows this rule as well.

The way the above congruence flows into this is if they are congrurnt to 1, decreasing the exponent by 1 is taking the multiplicative inverse.