prove by fermat-euler

**notyeteuler** · May 11th 2008, 12:42 AM

Fermat's Little Theorem has a very nice proof ...

Take $p$ is prime and $x>0$ . (You have already stated that $p$ does not divide $x$ ).
You can easily prove that $\left\{x,2x,...,(p-1)x\right\}=\left\{1,2,...,p-1\right\}$ (a basic proof by contradiction should do the trick).
Hence it must be the case that $x*2x*...*(p-1)x\equiv_{p}1*2*...*(p-1)$ .
You can then collect the $x$ terms and observe that $x^{p-1}(1*2*...*(p-1)\equiv_{p}1*2*...*(p-1)$ .
From this it follows that $x^{p-1}\equiv_{p}1$ as required

Hope that helps

Paul

**ThePerfectHacker** · May 11th 2008, 07:44 AM

Say that $\gcd (x,n)=1$ and $n=mp$ .
If $x^{n-1}\equiv 1(\bmod p)$ then it means $x^{mp-1}\equiv 1(\bmod p)$ thus $x^{m-1}\equiv 1(\bmod p)$ .
If $x^{m-1}\equiv 1(\bmod p)$ then $\left ( x^{m-1} \right)^p \equiv 1(\bmod p)$ so $x^{mp -p}\equiv 1(\bmod p)$ thus $x^{n - 1}\equiv(\bmod p)$ .

We never used the condition $\gcd( m,p)=1$ anywhere. We do not need it. Generalize this to several primes.

Thread: prove by fermat-euler

LinkBack

Thread Tools

Display

prove by fermat-euler

Similar Math Help Forum Discussions

abstract algebra [primitive root mod n, euler theorem, fermat theorem]

Working with mod p (Euler's and Fermat's Theorem)

Use induction to prove Fermat's Little Theorem

wats the relation between Fermat, Euler, Euler–Jacobi

fermat,euler,or CRT?

Search Tags