Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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