2
$\begingroup$

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}$ ?

  • 1
    Can 2 numbers strictly between 0 and m be congruent to each other modulo m?2011-12-09
  • 0
    @Ted, yes, if they're equal.2011-12-09
  • 0
    not modulo m but modulo totient of m2011-12-09
  • 0
    @gurghet, what? You don't need to do anything modulo the totient.2011-12-09
  • 0
    yes you're right i'm starting to get the picture2011-12-09

1 Answers 1