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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .