1. Not finding help here? Sign up for a free 30min 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!

Modular Arithemetic Question

  1. Feb 18, 2012 #1
    For n in N (Natural Numbers), use modular arithemetic to establish each of the following divisibility statements:

    a) 7 | 52n + 3 (25n - 2)

    Attempt: Well I've set up a mod 7 table and was figuring out the values from n = 0,....6 for the two individual expressions, then I was going to combine them. But I of course hit a rough patch when I got to 25n - 2. Since I'm in the Natural numbers, fractions do not exist, so how do I treat 25n - 2 when n = 0 ?
     
  2. jcsd
  3. Feb 18, 2012 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi trap101! :smile:
    some people include 0 in the natural numbers, and some don't

    clearly, this question doesn't

    see http://en.wikipedia.org/wiki/Natural_numbers#Notation for a discussion :wink:
     
  4. Feb 18, 2012 #3
    ahh this is true. I gather you would deduce this from the fact that I would have been stuck with a fraction if n = 0 did exist? So if n = 0 was included in the natural numbers for this question, would the question even be answerable?
     
  5. Feb 19, 2012 #4
    7 is a prime number, so Z7 is a finite field, and each non-zero element thus has a multiplicative inverse. You would treat 2-2 as 4 * 4 mod 7 in this case.
     
    Last edited: Feb 19, 2012
  6. Feb 19, 2012 #5
    ok thanks
     
  7. Feb 24, 2012 #6
    I had another quick question pertaining to this sort of question. The question asked me to establish that the above expression is true. Is the only way I can establish its truth by using a mod table or is there another method?
     
  8. Feb 24, 2012 #7
    Last edited: Feb 24, 2012
  9. Feb 24, 2012 #8

    Deveno

    User Avatar
    Science Advisor

    you shouldn't have to use a table.

    52n = (52)n, whether mod 7 or not.

    but mod 7, we can reduce 52 = 25 to 4. that is:

    52n = 4n (mod 7).

    now 3(25n-2) = 3(25)n(2-2).

    reduce everything on the right you can mod 7,

    you will have (3)(somethingn)(42) (mod 7).

    if you did everything right, you should be able to add the terms and it will be obvious what you have is equal to 0 mod 7, thus proving the orginial statement.
     
  10. Feb 25, 2012 #9


    Thanks. I got an answer, but my approach was a long winded table. Now I was trying to reduce how you suggested and I got (3)(4n 42 (mod 7).

    I made bold the 42 because I don't see where you got that from, as well what happened to the 2-2 portion?

    Now adding up these congruences I got 4n(1 + 19)....should that have been 4n(1+20), to get 21 and thus proving divisibility by 7?
     
  11. Feb 26, 2012 #10

    Deveno

    User Avatar
    Science Advisor

    mod 7, we have:

    (2)(4) = 8 = 1 (mod 7).

    therefore 2-1 = 4

    4 is the ONLY number x in {1,2,3,4,5,6} with this property: 2x = 1 (mod 7), which you may check if you like. it therefore makes sense to speak of 4 as THE inverse for 2 (mod 7).

    so if 2-1 = 4 (mod 7)

    then 2-2 = (2-1)2 = 42 (mod 7).

    it may come as no surprise that we can "multiply mod n". what IS no doubt surprising, is sometimes, we can also "divide mod n".

    in fact, if n is prime (as 7 so conveniently happens to be), we can divide by any non-zero residue class. that is, the integers modulo p (where p is prime) form a FIELD.

    mod 7 we have:

    1-1 = 1
    2-1 = 4
    3-1 = 5
    4-1 = 2
    5-1 = 3
    6-1 = 6.

    now, to finish "my approach" what is 16 (mod 7), and therefore, what is (3)(42) (mod 7)?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Modular Arithemetic Question
  1. Modular arithmetic (Replies: 3)

  2. Modular Inverses (Replies: 2)

Loading...