Number theory: ( remainder theorem.)

[mtayab1994]

Homework Statement

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)

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?

 

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

 

[mtayab1994]

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.

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?

 

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

 

[mtayab1994]

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?

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.

 

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

 

[mtayab1994]

Let me observe then that:

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

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

 

[I like Serena]

Yep.

 

[mtayab1994]

Yep.

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

 

[I like Serena]

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

 

[mtayab1994]

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

Why the 1(mod5).

 

[I like Serena]

So...

 

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

 

[I like Serena]

Yep.

 

[mtayab1994]

Yep.

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

 

[I like Serena]

Yes.

 

[mtayab1994]

Yes.

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

 

[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)?

 

[mtayab1994]

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)?

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??

 

[I like Serena]

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

 

[mtayab1994]

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

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?

 

[I like Serena]

Yes.
So you did have more information on mod calculations!

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

 

[mtayab1994]

Yes.
So you did have more information on mod calculations!

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

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.

 

[I like Serena]

Yep. That is correct.
Good that you want to learn more!

 

[mtayab1994]

Yep. That is correct.
Good that you want to learn more!

That's for all of your help.