Remainders by modular arithmatic

[trap101]

find the remainders for

a) 2²⁹³\equiv x (mod 15)

b) 243¹⁰¹\equiv x(mod 8)

c) 5²⁰⁰¹ + (27)! \equiv x (mod 8)


a) I was able to equate 2\equiv-13(mod15) ==> 2²\equiv4(mod15)

my idea here was to get 2⁹ 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.

help please...

 

[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!

 

[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 10⁵ + 7 x 10⁴ +...+ a x 10 + 1

working out the mods of the 10's I got

10 \equiv 2(mod 8)
10²\equiv 4(mod 8)
10³, 10⁴, 10⁵ 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.

 

[Dick]

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 10⁵ + 7 x 10⁴ +...+ a x 10 + 1

working out the mods of the 10's I got

10 \equiv 2(mod 8)
10²\equiv 4(mod 8)
10³, 10⁴, 10⁵ 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.

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?