Results 1 to 5 of 5

Thread: 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.

    $\displaystyle 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
    10
    You want to prove,
    $\displaystyle n^5-n$ is divisible by 5 (which is true this is Fermat's Little Theorem).

    You can factor,
    $\displaystyle 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,
    $\displaystyle 5k,5k+1,5k+2,5k+3,5k+4$
    If $\displaystyle n=5k$ that is clearly true because it has a factor $\displaystyle n=5k$. If $\displaystyle n=5k+1$ that is true because it has factor $\displaystyle n-1=5k$. If $\displaystyle n=5k+4$ that is true because it has factor $\displaystyle n+1=5k+4=5(k+1)$. Now it remains to show that $\displaystyle n=5k+2,5k+3=5k\pm 2$ when squared is $\displaystyle 5k+4$ add 1 in $\displaystyle n^2+1$ and you get the form of $\displaystyle 5k$
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, SKooT1027!

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

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

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


    We have: .$\displaystyle \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: .$\displaystyle k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 \;\equiv \;k + 1\pmod{5}$

    Therefore: .$\displaystyle (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: Oct 19th 2011, 06:16 PM
  2. Correct proof?
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Jul 12th 2011, 01:14 PM
  3. Is this proof correct?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jul 23rd 2010, 07:04 AM
  4. Is this proof correct?
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Mar 8th 2010, 02:34 PM
  5. lcm, gcd proof correct?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 26th 2010, 06:32 AM

Search Tags


/mathhelpforum @mathhelpforum