Results 1 to 5 of 5

Math Help - Proof of n^5 = n mod 5 .. is this correct?

  1. #1
    Newbie
    Joined
    Oct 2006
    Posts
    4

    Proof of n^5 = n mod 5 .. is this correct?

    I am not sure if this is a legit thing to do, so a second opinion would be nice .. also if u see any better/easier ways to do it, please let me know:

    Prove that n^5 is congruent (will be denoted by =) to n mod 5

    PMI
    Basis: 1^5 = 1 = 1 mod 5 as needed

    Inductive:
    Assume k^5 = k mod n
    k^5 + 1^5 = k mod 5 + 1^5 (this and the next step are the ones i question)
    so k^5 + 1 ^5 = k mod 5 + 1 mod 5 (bc 1^5 is always = 1 mod 5)
    So (k+1)^5 = (k+1) mod 5 as needed

    is this ok?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by SKooT1027 View Post
    I am not sure if this is a legit thing to do, so a second opinion would be nice .. also if u see any better/easier ways to do it, please let me know:

    Prove that n^5 is congruent (will be denoted by =) to n mod 5

    PMI
    Basis: 1^5 = 1 = 1 mod 5 as needed

    Inductive:
    Assume k^5 = k mod n
    k^5 + 1^5 = k mod 5 + 1^5 (this and the next step are the ones i question)
    so k^5 + 1 ^5 = k mod 5 + 1 mod 5 (bc 1^5 is always = 1 mod 5)
    So (k+1)^5 = (k+1) mod 5 as needed

    is this ok?
    No.

    k^5+1^5\neq (k+1)^5
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2006
    Posts
    4
    Err ok.. now that i read it, it makes it pretty obvious.. i was trying to use a proposition from my text that i didnt realize didnt hold bc of those powers

    What would be a better way of going about showing n^5 = n mod 5? I assume induction isnt the best way, but it was the only thing i thought of
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    You want to prove,
    n^5-n is divisible by 5 (which is true this is Fermat's Little Theorem).

    You can factor,
    n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=n(n-1)(n+1)(n^2+1)

    A number has 5 different forms,
    5k,5k+1,5k+2,5k+3,5k+4
    If n=5k that is clearly true because it has a factor n=5k. If n=5k+1 that is true because it has factor n-1=5k. If n=5k+4 that is true because it has factor n+1=5k+4=5(k+1). Now it remains to show that n=5k+2,5k+3=5k\pm 2 when squared is 5k+4 add 1 in n^2+1 and you get the form of 5k
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,548
    Thanks
    540
    Hello, SKooT1027!

    Prove that n^5 \equiv n \pmod{5}

    S(1): \;1^5 \equiv 1 \pmod{5}

    Assume S(k):\;k^5 \equiv k \pmod {5}


    We have: . \begin{array}{cccccc}k^5\\ 5k^4 \\ 10k^3  \\ 10k^2 \\ 5k \\ 1\end{array}\begin{array}{cccccc}\equiv \;k \pmod{5} \\ \equiv \;0\pmod{5}\\ \equiv \;0\pmod{5}\\ \equiv\;0\pmod{5} \\ \equiv\;0\pmod{5} \\ \equiv\;1\pmod{5}\end{array}

    Add: . k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 \;\equiv \;k + 1\pmod{5}

    Therefore: . (k+1)^5\;\equiv\;k+1\pmod{5}

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is my proof correct?
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: October 19th 2011, 06:16 PM
  2. Correct proof?
    Posted in the Calculus Forum
    Replies: 1
    Last Post: July 12th 2011, 01:14 PM
  3. Is this proof correct?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 23rd 2010, 07:04 AM
  4. Is this proof correct?
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: March 8th 2010, 02:34 PM
  5. lcm, gcd proof correct?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 26th 2010, 06:32 AM

Search Tags


/mathhelpforum @mathhelpforum