What is the remainder when 4101 is divided by 101?

[Saitama]

Homework Statement

Hi!
This is not a homework question but it came in my test.
What is the remainder when 4¹⁰¹ is divided by 101?

Homework Equations

(1+x)ⁿ-1 is always divisible by x.

The Attempt at a Solution

Only the equation given above came in my mind but i wasn't able to bring it in that form. I am not able to devise other way to solve it.

Thanks!

 

[I like Serena]

Hi Pranav-Arora!

The easiest way to do this, is with Fermat's little theorem or Euler's theorem (see wiki).

Most applicable here is Fermat's little theorem that says:
For any prime p holds: a^p \equiv a \mod p

(Do you already know about this notation or should I explain? )Btw, is this IIT stuff or something?

 

[Saitama]

Hi Pranav-Arora!

The easiest way to do this, is with Fermat's little theorem or Euler's theorem (see wiki).

Most applicable here is Fermat's little theorem that says:
For any prime p holds: a^p \equiv a \mod p

(Do you already know about this notation or should I explain? )Btw, is this IIT stuff or something?

Hi I Like Serena!

Sorry! But i don't know about Fermat's little theorem or Euler's theorem.
And yes, it may be from the IIT previous year question papers because most of the time my teacher try to make us solve IIT paper like questions.

 

[Saitama]

(Do you already know about this notation or should I explain? )

It would be much appreciated if you explain me the notation.

 

[I like Serena]

Sorry! But i don't know about Fermat's little theorem or Euler's theorem.
And yes, it may be from the IIT previous year question papers because most of the time my teacher try to make us solve IIT paper like questions.

Well, I don't know what is expected from you here.
Or whether you should know about these theorems already.
Typically it would be first year university mathematics material (algebra).

Actually there is an alternate way to do this for which you do not need to know these theorems. It's just more work.

If we take for instance 4³ and divide it by 10, we can also take the remainder of 4² divided by 10, multiply it by 4 and take the remainder again.
The remainder of 4²=16 is 6, multiplied by 4 is 24, and the remainder of 24 is 4.

It would be much appreciated if you explain me the notation.

a \equiv b \mod c is about the remainders in divisions.

For instance 10 \equiv 1 \mod 3 means that if you divide 10 by 3, the remainder is 1.
And it is actually more generic, because you can also say 10 \equiv 4 \mod 3, mearning that the remainders of 10 resp. 4 when divided by 3 are the same.
I guess I shouldn't explain the theorems as they are probably out of scope for your current class material.
Still, if you're interested, here goes:

Wiki also states Fermat's little theorem without this notation: "Fermat's little theorem states that if p is a prime number, then for any integer a, a^p − a will be evenly divisible by p. "

101 is a prime, meaning that it is only divisible by 1 and by itself.

Since 101 is a prime, this means that 4¹⁰¹ - 4 divided by 101 has remainder 0.

 

[Saitama]

Well, I'm don't know what is expected from you here.
Or whether you should know about these theorems already.
Typically it would be first year university mathematics material (algebra).

Actually there is an alternate way to do this for which you do not need to know these theorems. It's just more work.

If we take for instance 4³ and divide it by 10, we can also take the remainder of 4² divided by 10, multiply it by 4 and take the remainder again.
The remainder of 4²=16 is 6, multiplied by 4 is 24, and the remainder of 24 is 4.




a \equiv b \mod c is about the remainders in divisions.

For instance 10 \equiv 1 \mod 3 means that if you divide 10 by 3, the remainder is 1.
And it is actually more generic, because you can also say 10 \equiv 4 \mod 3, mearning that the remainders of 10 resp. 4 when divided by 3 are the same.



I guess I shouldn't explain the theorems as they are probably out of scope for your current class material.
Still, if you're interested, here goes:

Wiki also states Fermat's little theorem without this notation: "Fermat's little theorem states that if p is a prime number, then for any integer a, a^p − a will be evenly divisible by p. "

101 is a prime, meaning that it is only divisible by 1 and by itself.

Since 101 is a prime, this means that 4¹⁰¹ - 4 divided by 101 has remainder 0.

Thanks for your explanation!
So if i do it like this, subtract and add 4 to 4¹⁰¹, what i get is this:-
4¹⁰¹-4+4
As you said that 4¹⁰¹-4 is completely divisible by 101, so here +4 is left. Therefore the remainder is 4.
Am i right..?

 

[I like Serena]

Thanks for your explanation!
So if i do it like this, subtract and add 4 to 4¹⁰¹, what i get is this:-
4¹⁰¹-4+4
As you said that 4¹⁰¹-4 is completely divisible by 101, so here +4 is left. Therefore the remainder is 4.
Am i right..?

Yep!

 

[Saitama]

Yep!

Thanks!
I would also like to know where this Fermat's little theorem is applicable. Would you please tell me?

 

[I like Serena]

Thanks!
I would also like to know where this Fermat's little theorem is applicable. Would you please tell me?

It's applicable whenever you have a problem with numbers involving remainders and exponentiation!

Application in real life is typically in cryptography.
It is used (actually the generalization Euler's theorem) in the RSA encryption technique (http://en.wikipedia.org/wiki/RSA).
This encryption scheme is used world wide for all secure communication across the internet.

 

[Saitama]

When i checked wikipedia, it isn't stated anywhere that "Fermat's little theorem states that if p is a prime number, then for any integer a, a^p − a will be evenly divisible by p. " Rather it is stated "if p is a prime and a is an integer coprime to p, then a^p−1 − 1 will be evenly divisible by p."

 

[I like Serena]

When i checked wikipedia, it isn't stated anywhere that "Fermat's little theorem states that if p is a prime number, then for any integer a, a^p − a will be evenly divisible by p. " Rather it is stated "if p is a prime and a is an integer coprime to p, then a^p−1 − 1 will be evenly divisible by p."

Are you looking at the same page I did?
http://en.wikipedia.org/wiki/Fermat's_little_theorem

What you mention is the alternate form, which is mentioned in the wiki page right after the text I quoted.
I prefer the version I quoted, since it does not put a constraint on "a".
(And I didn't have to explain what "coprime" means.)

 

[Saitama]

Are you looking at the same page I did?
http://en.wikipedia.org/wiki/Fermat's_little_theorem

Yes, i am looking at the same page. When i tried to solve using this statement " if p is a prime and a is an integer coprime to p, then a p−1 − 1 will be evenly divisible by p." then too i got the remainder 4.

What you mention is the alternate form, which is mentioned in the wiki page right after the text I quoted.

Oops! I didn't noticed it!

I prefer the version I quoted, since it does not put a constraint on "a".
(And I didn't have to explain what "coprime" means.)

And yes i know what a coprime is.