Results 1 to 3 of 3

Thread: prove by fermat-euler

  1. #1
    Senior Member
    Joined
    Feb 2008
    Posts
    321

    prove by fermat-euler

    Attached Thumbnails Attached Thumbnails prove by fermat-euler-1.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2008
    Posts
    17
    Fermat's Little Theorem has a very nice proof ...

    Take $\displaystyle p$ is prime and $\displaystyle x>0$. (You have already stated that $\displaystyle p$ does not divide $\displaystyle x$).
    You can easily prove that $\displaystyle \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 $\displaystyle x*2x*...*(p-1)x\equiv_{p}1*2*...*(p-1)$.
    You can then collect the $\displaystyle x$ terms and observe that $\displaystyle x^{p-1}(1*2*...*(p-1)\equiv_{p}1*2*...*(p-1)$.
    From this it follows that $\displaystyle x^{p-1}\equiv_{p}1$ as required

    Hope that helps

    Paul
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Say that $\displaystyle \gcd (x,n)=1$ and $\displaystyle n=mp$.
    If $\displaystyle x^{n-1}\equiv 1(\bmod p)$ then it means $\displaystyle x^{mp-1}\equiv 1(\bmod p)$ thus $\displaystyle x^{m-1}\equiv 1(\bmod p)$.
    If $\displaystyle x^{m-1}\equiv 1(\bmod p)$ then $\displaystyle \left ( x^{m-1} \right)^p \equiv 1(\bmod p)$ so $\displaystyle x^{mp -p}\equiv 1(\bmod p)$ thus $\displaystyle x^{n - 1}\equiv(\bmod p)$.

    We never used the condition $\displaystyle \gcd( m,p)=1$ anywhere. We do not need it. Generalize this to several primes.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: Jan 10th 2011, 08:51 AM
  2. Working with mod p (Euler's and Fermat's Theorem)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Apr 22nd 2010, 11:22 PM
  3. Use induction to prove Fermat's Little Theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Mar 8th 2010, 05:36 PM
  4. Replies: 0
    Last Post: Sep 17th 2009, 06:44 PM
  5. fermat,euler,or CRT?
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Jan 4th 2008, 02:08 PM

Search Tags


/mathhelpforum @mathhelpforum