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!

Number theory: ( remainder theorem.)

  1. Apr 28, 2012 #1
    1. The problem statement, all variables and given/known data

    A) Find the remainder of 2^n and 3^n when divided by 5.

    B)Conclude the remainder of 2792^217 when divided by 5.

    C)solve in N the following : 1) 7^n+1 Ξ 0(mod5)
    2) 2^n+3^n Ξ 0(mod5)



    3. The attempt at a solution


    A) I know that for the first two I have to get 2^n=5k+r and 3^n=5k+r where r is a remainder, but how do i finish it off?? Do I just chose values of n and keep trying and see what I get or what??

    Like for (2^n)/5 so we give n values of 0,1,2,3,4 and then we get

    n=0 : 1/5 = 0k+1
    n=1 : 2/5 = 0k+2
    n=2 : 4/5 = 0k+4
    n=3 : 8/5 = 1k+3 or 2k-2
    n=4 : 16/5 = 3k+1 or 4k-4

    Can we say that the remainders are -4,-3,-2,1,2,3,4?
     
    Last edited: Apr 28, 2012
  2. jcsd
  3. Apr 28, 2012 #2

    I like Serena

    User Avatar
    Homework Helper

    Hi mtayab1994! :smile:

    I think that for (A) you are supposed to make a table for n, 2^n (mod 5), and 3^n (mod 5) for all values of n, or rather until the values start repeating.

    Btw, note that a remainder of -1 is the same as the remainder 4.
     
  4. Apr 28, 2012 #3
    Yes i know that and so is -2 and 3 but our teacher likes us to represent them all. And by the way for B how can i do that the same concept as the first one right?
     
  5. Apr 28, 2012 #4

    I like Serena

    User Avatar
    Homework Helper

    For (B) you need to use calculation rules for remainders.
    You don't actually need (A) for that, although it helps to see that the remainder of 2^n restarts after a couple of values.

    Which calculation rules do you know?
    Do you know for instance that ##a\cdot b \equiv (a \pmod n) \cdot (b \pmod n) \mod n## if a,b, and n are relatively prime?
     
  6. Apr 28, 2012 #5
    Nope don't know that still haven't covered it but i do know that if a Ξ b(modn) and c Ξ d(modn)
    then ac Ξ bd(modn) and many others in that kind of form , but nothing like you stated.
     
  7. Apr 28, 2012 #6

    I like Serena

    User Avatar
    Homework Helper

    Let me observe then that:

    2792^217 Ξ (2790+2)^217 Ξ (sum of factors with 2790 in it) + 2^217 Ξ 0 + 2^217 (mod 5)
     
  8. Apr 28, 2012 #7
    So now all i have to do is see the remainder of 2^217 when divided by 5 right?
     
  9. Apr 28, 2012 #8

    I like Serena

    User Avatar
    Homework Helper

  10. Apr 28, 2012 #9
    Yes and now i have to see what the remainder of 2 over 5 when 2 is raised to the power of 217.
     
  11. Apr 28, 2012 #10

    I like Serena

    User Avatar
    Homework Helper

    You should already have that 2^4 Ξ 1 (mod 5).
    What is 2^8?
    And 2^12?
     
  12. Apr 28, 2012 #11
    Why the 1(mod5).
     
  13. Apr 28, 2012 #12

    I like Serena

    User Avatar
    Homework Helper

  14. Apr 28, 2012 #13
    I get it so (2^216)/5 will give a remainder of 1. Hence 2^217 will give a remainder 2. Am I right??
     
  15. Apr 28, 2012 #14

    I like Serena

    User Avatar
    Homework Helper

  16. Apr 28, 2012 #15
    Ok and any hint on C. Should I use the same thing i did with A.
     
  17. Apr 28, 2012 #16

    I like Serena

    User Avatar
    Homework Helper

  18. Apr 28, 2012 #17
    7^n+1 Ξ 0(mod5) is correct for values of 2 and 10 and many other values but how do i represent it?
     
  19. Apr 28, 2012 #18

    I like Serena

    User Avatar
    Homework Helper

    Let's try to solve that expression.
    The first step is to break it up into a simpler expression.

    7^n+1=(5+2)^n+1

    Can you rewrite (5+2)^n?
    Of if you can't, see what happens for n=0,1,2,3,4 (mod 5)?
     
  20. Apr 28, 2012 #19
    For 7^n we get the following remainders:

    7^0 = 1
    7^1 = 2
    7^2 = 4
    7^3 = 3

    And then they keep on repeating.
    So: 7^n Ξ 4(mod5) holds if n=2(mod4) so n= 2+4k for some integer k. Is that correct??
     
  21. Apr 28, 2012 #20

    I like Serena

    User Avatar
    Homework Helper

    Yep.
    You can also write it in mod-notation: nΞ2 (mod 4).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook