Results 1 to 3 of 3

Thread: Fermat's little theorem

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,114
    Thanks
    7

    Fermat's little theorem

    Use Fermat's theorem to show that for any positive integer n, the integer $\displaystyle n^{37}-n$ is divisible by 383838.

    My attempt:

    383838=(37)(19)(13)(7)(3)(2)

    If 37 does not divide n, then by FLT, $\displaystyle n^{36} \equiv 1\ (mod\ 37)$. If, however, 37 divides n, then $\displaystyle n \equiv 0\ (mod\ 37)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 37)$.

    If 19 does not divide p, then by FLT, $\displaystyle n^{18} \equiv 1\ (mod\ 19)\implies n^{36} \equiv 1\ (mod\ 19)$. If, however, 19 divides n, then $\displaystyle n \equiv 0\ (mod\ 19)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 19)$.

    If 13 does not divide p, then by FLT, $\displaystyle n^{12} \equiv 1\ (mod\ 13)\implies n^{36} \equiv 1\ (mod\ 13)$. If, however, 37 divides n, then $\displaystyle n \equiv 0\ (mod\ 13)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 13)$.

    If 7 does not divide p, then by FLT, $\displaystyle n^6 \equiv 1\ (mod\ 13)\implies n^{36} \equiv 1\ (mod\ 7)$. If, however, 7 divides n, then $\displaystyle n \equiv 0\ (mod\ 7)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 7)$.

    If 3 does not divide p, then by FLT, $\displaystyle n^2 \equiv 1\ (mod\ 3)\implies n^{36} \equiv 1\ (mod\ 3)$. If, however, 3 divides n, then $\displaystyle n \equiv 0\ (mod\ 3)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 3)$.

    If 2 does not divide p, then by FLT, $\displaystyle n \equiv 1\ (mod\ 2)\implies n^{36} \equiv 1\ (mod\ 2)$. If, however, 2 divides n, then $\displaystyle n \equiv 0\ (mod\ 2)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 2)$.

    Combining these 6 congruences, we get

    $\displaystyle n^{37} \equiv n\ (mod\ 383838)$

    Could someone please check my proof? Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Fermat's little theorem

    Quote Originally Posted by alexmahone View Post
    Use Fermat's theorem to show that for any positive integer n, the integer $\displaystyle n^{37}-n$ is divisible by 383838.

    My attempt:

    383838=(37)(19)(13)(7)(3)(2)

    If 37 does not divide n, then by FLT, $\displaystyle n^{36} \equiv 1\ (mod\ 37)$. If, however, 37 divides n, then $\displaystyle n \equiv 0\ (mod\ 37)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 37)$.

    If 19 does not divide p, then by FLT, $\displaystyle n^{18} \equiv 1\ (mod\ 19)\implies n^{36} \equiv 1\ (mod\ 19)$. If, however, 19 divides n, then $\displaystyle n \equiv 0\ (mod\ 19)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 19)$.

    If 13 does not divide p, then by FLT, $\displaystyle n^{12} \equiv 1\ (mod\ 13)\implies n^{36} \equiv 1\ (mod\ 13)$. If, however, 37 divides n, then $\displaystyle n \equiv 0\ (mod\ 13)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 13)$.

    If 7 does not divide p, then by FLT, $\displaystyle n^6 \equiv 1\ (mod\ 13)\implies n^{36} \equiv 1\ (mod\ 7)$. If, however, 7 divides n, then $\displaystyle n \equiv 0\ (mod\ 7)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 7)$.

    If 3 does not divide p, then by FLT, $\displaystyle n^2 \equiv 1\ (mod\ 3)\implies n^{36} \equiv 1\ (mod\ 3)$. If, however, 3 divides n, then $\displaystyle n \equiv 0\ (mod\ 3)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 3)$.

    If 2 does not divide p, then by FLT, $\displaystyle n \equiv 1\ (mod\ 2)\implies n^{36} \equiv 1\ (mod\ 2)$. If, however, 2 divides n, then $\displaystyle n \equiv 0\ (mod\ 2)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 2)$.

    Combining these 6 congruences, we get

    $\displaystyle n^{37} \equiv n\ (mod\ 383838)$

    Could someone please check my proof? Thanks in advance.

    Correct!

    Edit: Perhaps you need to mention the use of Chinese reminder theorem in the last stage.
    Last edited by Also sprach Zarathustra; Jul 16th 2011 at 04:28 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2011
    Posts
    19

    Re: Fermat's little theorem

    A little prove for Fermat's theorem:Consider$\displaystyle (Z_p^*,\cdot)$ is a group with p-1 elements so from a corollary of Lagrange's theorem $\displaystyle \hat{x}^{p-1}=\hat{1} \Rightarrow x^p\equiv x(modp)$
    Another way to prove is considering we have p pearls of a colours and $\displaystyle a^p$ strings .If we throw away the monocolour strings we have $\displaystyle a^p-a$ strings.Now we connect the ends of each string and results a necklace.knowing that a necklace doesn't differ by a rotation we have $\displaystyle \frac{a^p-a}{p}$ different necklaces hence the conclusion.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 12th 2011, 05:28 AM
  2. Replies: 4
    Last Post: Jan 10th 2011, 08:51 AM
  3. Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jun 18th 2010, 01:33 AM
  4. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jan 11th 2010, 08:43 AM
  5. Fermat's Last Theorem
    Posted in the Advanced Math Topics Forum
    Replies: 13
    Last Post: Jul 21st 2007, 06:23 PM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum