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

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I don’t understand the Chinese Remainder Theorem :( $\endgroup$
    – gurghet
    May 22, 2018 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.