# Remainders by modular arithmatic

1. Feb 23, 2013

### trap101

find the remainders for

a) 2293$\equiv$ x (mod 15)

b) 243101$\equiv$ x(mod 8)

c) 52001 + (27)! $\equiv$ x (mod 8)

a) I was able to equate 2$\equiv$-13(mod15) ==> 22$\equiv$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 $\equiv$ 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.

2. Feb 23, 2013

### Dick

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!

3. Feb 23, 2013

### trap101

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 $\equiv$ 2(mod 8)
102$\equiv$ 4(mod 8)
103, 104, 105 were all $\equiv$ 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.

4. Feb 23, 2013

### Dick

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?