# Number theory: ( remainder theorem.)

1. Apr 28, 2012

### mtayab1994

1. The problem statement, all variables and given/known data

A) Find the remainder of 2^n and 3^n when divided by 5.

B)Conclude the remainder of 2792^217 when divided by 5.

C)solve in N the following : 1) 7^n+1 Ξ 0(mod5)
2) 2^n+3^n Ξ 0(mod5)

3. The attempt at a solution

A) I know that for the first two I have to get 2^n=5k+r and 3^n=5k+r where r is a remainder, but how do i finish it off?? Do I just chose values of n and keep trying and see what I get or what??

Like for (2^n)/5 so we give n values of 0,1,2,3,4 and then we get

n=0 : 1/5 = 0k+1
n=1 : 2/5 = 0k+2
n=2 : 4/5 = 0k+4
n=3 : 8/5 = 1k+3 or 2k-2
n=4 : 16/5 = 3k+1 or 4k-4

Can we say that the remainders are -4,-3,-2,1,2,3,4?

Last edited: Apr 28, 2012
2. Apr 28, 2012

### I like Serena

Hi mtayab1994!

I think that for (A) you are supposed to make a table for n, 2^n (mod 5), and 3^n (mod 5) for all values of n, or rather until the values start repeating.

Btw, note that a remainder of -1 is the same as the remainder 4.

3. Apr 28, 2012

### mtayab1994

Yes i know that and so is -2 and 3 but our teacher likes us to represent them all. And by the way for B how can i do that the same concept as the first one right?

4. Apr 28, 2012

### I like Serena

For (B) you need to use calculation rules for remainders.
You don't actually need (A) for that, although it helps to see that the remainder of 2^n restarts after a couple of values.

Which calculation rules do you know?
Do you know for instance that $a\cdot b \equiv (a \pmod n) \cdot (b \pmod n) \mod n$ if a,b, and n are relatively prime?

5. Apr 28, 2012

### mtayab1994

Nope don't know that still haven't covered it but i do know that if a Ξ b(modn) and c Ξ d(modn)
then ac Ξ bd(modn) and many others in that kind of form , but nothing like you stated.

6. Apr 28, 2012

### I like Serena

Let me observe then that:

2792^217 Ξ (2790+2)^217 Ξ (sum of factors with 2790 in it) + 2^217 Ξ 0 + 2^217 (mod 5)

7. Apr 28, 2012

### mtayab1994

So now all i have to do is see the remainder of 2^217 when divided by 5 right?

8. Apr 28, 2012

### I like Serena

Yep.

9. Apr 28, 2012

### mtayab1994

Yes and now i have to see what the remainder of 2 over 5 when 2 is raised to the power of 217.

10. Apr 28, 2012

### I like Serena

You should already have that 2^4 Ξ 1 (mod 5).
What is 2^8?
And 2^12?

11. Apr 28, 2012

### mtayab1994

Why the 1(mod5).

12. Apr 28, 2012

### I like Serena

So...

13. Apr 28, 2012

### mtayab1994

I get it so (2^216)/5 will give a remainder of 1. Hence 2^217 will give a remainder 2. Am I right??

14. Apr 28, 2012

### I like Serena

Yep.

15. Apr 28, 2012

### mtayab1994

Ok and any hint on C. Should I use the same thing i did with A.

16. Apr 28, 2012

### I like Serena

Yes.

17. Apr 28, 2012

### mtayab1994

7^n+1 Ξ 0(mod5) is correct for values of 2 and 10 and many other values but how do i represent it?

18. Apr 28, 2012

### I like Serena

Let's try to solve that expression.
The first step is to break it up into a simpler expression.

7^n+1=(5+2)^n+1

Can you rewrite (5+2)^n?
Of if you can't, see what happens for n=0,1,2,3,4 (mod 5)?

19. Apr 28, 2012

### mtayab1994

For 7^n we get the following remainders:

7^0 = 1
7^1 = 2
7^2 = 4
7^3 = 3

And then they keep on repeating.
So: 7^n Ξ 4(mod5) holds if n=2(mod4) so n= 2+4k for some integer k. Is that correct??

20. Apr 28, 2012

### I like Serena

Yep.
You can also write it in mod-notation: nΞ2 (mod 4).