# How to go from Fermat’s little theorem to Euler’s theorem thought Ivory’s demonstration?

Ivory’s demonstration of Fermat’s theorem exploit the fact that given a prime $p$, all the numbers from $1$ to $p-1$ are relatively prime to $p$ (obvious since $p$ is prime). Ivory multiply them by x and he gets:

$(x)(2x)\cdots((p-1)x)\equiv(1)(2)\cdots(p-1)\pmod{p}$

which gives the theorem since I can cancel all the integers and leave:

$x^{p-1}\equiv1\pmod{p}$.

To derive Euler’s theorem I should switch to modulus $m$ non-prime and take the positive integers relatively prime to $m$ and repeat the process. At this point I have $\phi(m)$ such numbers. How do I prove that they are all non congruent one another (to form a complete set of residues to the modulus $\phi(m)$) so that I can multiply them by an $x$ relatively prime to $m$ and repeat the same steps to prove

$x^{\phi(m)}\equiv1\pmod{m}$ ?

-
Can 2 numbers strictly between 0 and m be congruent to each other modulo m? –  Ted Dec 9 '11 at 9:01
@Ted, yes, if they're equal. –  Peter Taylor Dec 9 '11 at 9:29
not modulo m but modulo totient of m –  gurghet Dec 9 '11 at 10:30
@gurghet, what? You don't need to do anything modulo the totient. –  Peter Taylor Dec 9 '11 at 10:37
yes you're right i'm starting to get the picture –  gurghet Dec 9 '11 at 10:50

You have $a \ne b$ $\mod m$, $\gcd(a,m)=\gcd(b,m)=gcd(x,m)=1$.
Suppose $ax = bx \mod m$. Then you can use the Chinese Remainder Theorem and the fact that $x$ is coprime to $m$ to find a multiplicative inverse to $x \mod m$ and derive a contradiction.
To go beyond the actual question: this shows that multiplication by $x$ permutes the $\phi(m)$ numbers co-prime to $m$, so $$\prod_{a\in\{c | 0<c<m \wedge \gcd(c,m)=1\}} ax = \prod_{a\in\{c | 0<c<m \wedge \gcd(c,m)=1\}} a \mod m$$