Results 1 to 3 of 3

Math Help - Fermat's little theorem

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

    Fermat's little theorem

    Use Fermat's theorem to show that for any positive integer n, the integer 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, n^{36} \equiv 1\ (mod\ 37). If, however, 37 divides n, then n \equiv 0\ (mod\ 37). Thus in any case, n^{37} \equiv n\ (mod\ 37).

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

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

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

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

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

    Combining these 6 congruences, we get

    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 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, n^{36} \equiv 1\ (mod\ 37). If, however, 37 divides n, then n \equiv 0\ (mod\ 37). Thus in any case, n^{37} \equiv n\ (mod\ 37).

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

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

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

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

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

    Combining these 6 congruences, we get

    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; July 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 (Z_p^*,\cdot) is a group with p-1 elements so from a corollary of Lagrange's theorem \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 a^p strings .If we throw away the monocolour strings we have 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 \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: April 12th 2011, 05:28 AM
  2. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  3. Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2010, 01:33 AM
  4. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 11th 2010, 08:43 AM
  5. Fermat's Last Theorem
    Posted in the Advanced Math Topics Forum
    Replies: 13
    Last Post: July 21st 2007, 06:23 PM

Search Tags


/mathhelpforum @mathhelpforum