# What would be the remainder?

1. Jun 25, 2011

### Saitama

1. The problem statement, all variables and given/known data
Hi!!
This is not a homework question but it came in my test.
What is the remainder when 4101 is divided by 101?

2. Relevant equations
(1+x)n-1 is always divisible by x.

3. 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!!

2. Jun 25, 2011

### 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$

Btw, is this IIT stuff or something?

Last edited: Jun 25, 2011
3. Jun 25, 2011

### Saitama

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.

4. Jun 25, 2011

### Saitama

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

5. Jun 25, 2011

### I like Serena

Well, I don't know what is expected from you here.
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 43 and divide it by 10, we can also take the remainder of 42 divided by 10, multiply it by 4 and take the remainder again.
The remainder of 42=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, ap − 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 4101 - 4 divided by 101 has remainder 0.

Last edited: Jun 26, 2011
6. Jun 26, 2011

### Saitama

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

7. Jun 26, 2011

### I like Serena

Yep!

8. Jun 26, 2011

### Saitama

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

9. Jun 26, 2011

### I like Serena

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.

10. Jun 26, 2011

### 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, ap − 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 ap−1 − 1 will be evenly divisible by p."

11. Jun 26, 2011

### I like Serena

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

12. Jun 26, 2011

### Saitama

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.

Oops!! I didn't noticed it!!

And yes i know what a coprime is.