Homework Help: 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).

21. Apr 28, 2012

mtayab1994

Alright, I really appreciate your help, and by the way, $$b^{e}(modn)$$ are always periodic for fixed b.
If n is prime and $$(b,n)=1$$ then the period is p-1 (Fermats little theorem). That's what happens in all my cases right?

22. Apr 28, 2012

I like Serena

Yes.

That leaves the question whether you understood what I did to (B)...

23. Apr 28, 2012

mtayab1994

Yes I actually did after a bit of research:

2792 Ξ 2(mod5) using that if a Ξ b(modn) then a^k Ξ b^k(modn) we get:

2792^217 Ξ 2^217(mod5) and since the period is 4 because p-1=5-1=4 then:

2^217 Ξ 2^1 Ξ 2(mod5). Am I correct. I try doing the most amount of research and learning on my own, because education here in Morocco is really bad and teachers here don't care if you learn or not.

24. Apr 28, 2012

I like Serena

Yep. That is correct.

25. Apr 28, 2012

mtayab1994

That's for all of your help.