1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Congruence Modulo Proof

  1. Feb 27, 2014 #1
    1. The problem statement, all variables and given/known data
    Suppose n is an integer which is not a divisor of 5.
    Prove that ##n^{4} \equiv 1 mod5##

    3. The attempt at a solution
    I know that 16 mod 5 is equivalent to 1 mod5.

    ##16 = 2^{4}##

    2 is not a divisor of 5. How do I prove this for the general case?

    I know
    ##n^{4} -1 = 5k, ## for some k ##\in Z##
     
  2. jcsd
  3. Feb 27, 2014 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi knowLittle! :smile:

    (you mean, not a multiple of 5 ! :wink:)
    if you know that, then that's just another way of saying ##n^{4} \equiv 1 mod5##

    (otherwise, you know it for n = 2, and obviously for n = 1, so how many more cases do you need to prove?)
     
  4. Feb 27, 2014 #3
    Hi TINY-tim,

    The problem states divisor. Also, there's a typo in the ##\equiv## symbol; in the paper it shows '='.

    I understand that n=2 and n=1 and satisfies the statement. But, how do I prove this, I am confused as to how to prove this. I assume they want me to prove a general case?
     
  5. Feb 27, 2014 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi knowLittle! :smile:
    yes

    i don't know how much you know about mod calculations :confused:

    since you can prove it for n = 2 (because 16 - 1 = 15), does that help you with any other values of n ?

    and since it's obviously true for n = 1, does that help you with any other values of n ?

    and are there any other cases left?

    (alternatively, do you know Fermat's little theorem?)
     
  6. Feb 27, 2014 #5
    We didn't explicitly covered Fermat's theorem, but I will take a look. I am sure that the solution requires elementary knowledge, for we have not covered much.

    I am still lost :/
     
  7. Feb 27, 2014 #6

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    if 24 - 1 is divisble by 5, what can you say about (5n + 2)4 - 1 ? :smile:
     
  8. Feb 27, 2014 #7
    If 5n+2 is a multiple of 2, then ##(5n+2)^{4} -1 ## would be divisible by 5. Right?
     
  9. Feb 27, 2014 #8

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    right! :smile:

    and ##(5n+1)^{4} -1 ## ?

    and ##(5n-1)^{4} -1 ## ?

    and ##(5n-2)^{4} -1 ## ?

    what other cases do you need? :wink:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Congruence Modulo Proof
  1. Modulo Arithmatic (Replies: 2)

  2. Congruence problem. (Replies: 10)

  3. Linear congruence (Replies: 3)

  4. Modulo arithmetic (Replies: 5)

Loading...