Remainders by modular arithmatic

  • Thread starter trap101
  • Start date
  • #1
342
0
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.......
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,260
619
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
342
0
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.
 
  • #4
Dick
Science Advisor
Homework Helper
26,260
619
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.

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?
 

Related Threads on Remainders by modular arithmatic

  • Last Post
Replies
10
Views
1K
Replies
3
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
1K
Top