Number theory: ( remainder theorem.)

mtayab1994
Messages
584
Reaction score
0

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?
 
Last edited:
Physics news on Phys.org
Hi mtayab1994! :smile:

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.
 
I like Serena said:
Hi mtayab1994! :smile:

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?
 
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?
 
I like Serena said:
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.
 
Let me observe then that:

2792^217 Ξ (2790+2)^217 Ξ (sum of factors with 2790 in it) + 2^217 Ξ 0 + 2^217 (mod 5)
 
I like Serena said:
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?
 
Yep.
 
I like Serena said:
Yep.

Yes and now i have to see what the remainder of 2 over 5 when 2 is raised to the power of 217.
 
  • #10
You should already have that 2^4 Ξ 1 (mod 5).
What is 2^8?
And 2^12?
 
  • #11
I like Serena said:
You should already have that 2^4 Ξ 1 (mod 5).
What is 2^8?
And 2^12?

Why the 1(mod5).
 
  • #12
So...
 
  • #13
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
Yep.
 
  • #15
I like Serena said:
Yep.

Ok and any hint on C. Should I use the same thing i did with A.
 
  • #16
Yes.
 
  • #17
I like Serena said:
Yes.

7^n+1 Ξ 0(mod5) is correct for values of 2 and 10 and many other values but how do i represent it?
 
  • #18
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
I like Serena said:
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??
 
  • #20
Yep.
You can also write it in mod-notation: nΞ2 (mod 4).
 
  • #21
I like Serena said:
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?
 
  • #22
Yes.
So you did have more information on mod calculations! :wink:

That leaves the question whether you understood what I did to (B)...
 
  • #23
I like Serena said:
Yes.
So you did have more information on mod calculations! :wink:

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.
 
  • #24
Yep. That is correct.
Good that you want to learn more! :approve:
 
  • #25
I like Serena said:
Yep. That is correct.
Good that you want to learn more! :approve:

That's for all of your help.
 
Back
Top