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!

Homework Help: Remainders by modular arithmatic

  1. Feb 23, 2013 #1
    find the remainders for

    a) 2293[itex]\equiv[/itex] x (mod 15)

    b) 243101[itex]\equiv[/itex] x(mod 8)

    c) 52001 + (27)! [itex]\equiv[/itex] x (mod 8)

    a) I was able to equate 2[itex]\equiv[/itex]-13(mod15) ==> 22[itex]\equiv[/itex]4(mod15)

    my idea here was to get 29 and then multiply by a power of 100 which would give me 900 and then work out the other 23 from there, but I've already hit a road block....I'm going to end up with a huge number just from the product of the moduluses......maybe that's what is suppose to happen, but I'm under the assumption that I'm suppose to figure these out without a calculator.

    b) I was able to work it down to a congruence of 243 [itex]\equiv[/itex] 3(mod 8) but if I raise that to the 101 on both sides.....again I'm out of luck in terms of the 3.

    help please.......
  2. jcsd
  3. Feb 23, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper

    Try going up in larger steps by using powers. 2^2=4 mod 15. Square both sides, so 2^4=4^2=1 mod 15. You can get up to 2^8, 2^16 pretty easily by repeated squaring and taking mods. But look at 2^4=1 mod 15. That's pretty useful!
  4. Feb 23, 2013 #3
    Thanks I actually figured it out with that hint. I had one more question, but I didn't want to start a new thread for it:

    Show that their is no digit "a" such that the number 2794a1 is divisible by 8.

    So I tried to apply the rule that "every natural number is congruent to the sum of its digits modulo 9"

    Now I know this isn't 9, but I tried this:

    2 x 105 + 7 x 104 +.....+ a x 10 + 1

    working out the mods of the 10's I got

    10 [itex]\equiv[/itex] 2(mod 8)
    102[itex]\equiv[/itex] 4(mod 8)
    103, 104, 105 were all [itex]\equiv[/itex] 0 (mod 8)

    I have a feeling the other two are as well but I don't think I want to deal with negatives.

    Doing this and combining the info I obtained this expression after multiplying by the modulus and following the rules:

    = 4+a+1
    = 5 + a (mod 8)

    but obviously there are some values that will allow this to be divisble by 8, so I messed up somewhere.
  5. Feb 23, 2013 #4


    User Avatar
    Science Advisor
    Homework Helper

    Yeah, you messed up. You don't just want to add the digits, do you? The value mod 8 will be the value of each of the digits times the mod value of the corresponding power of 10. What equation do you really want to solve?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook