# Homework Help: Finding remainder

1. Jul 12, 2012

### Saitama

1. The problem statement, all variables and given/known data
Find the remainder of $\frac{25!}{29}$

2. Relevant equations

3. The attempt at a solution
One of my friend asked me this question and i was clueless how should i start?
(I am not sure that the question is correct.)

Any help is appreciated!

2. Jul 12, 2012

### Travis_King

??Find the remainder after you divide 25(Factorial) by 29.

Do you know what a factorial is? (the ! symbol)

3. Jul 12, 2012

### Saitama

I know what a factorial is. Wouldn't that be a difficult task, expanding 25! and dividing it by 29?

4. Jul 12, 2012

### Travis_King

Yea, I see your predicament. It's just a long number and would be a PITA to get at. But you take the nearest whole number from your result and multiply by 29. Subtract that from 25! and you'll get the remainder.

5. Jul 12, 2012

### HallsofIvy

I believe Pranav-Arora is asking if there is a simpler way of calculating that since 29! is a huge number. And trying to use a calculator won't work because dividing by 29 will give a non-terminating decimal and you cannot get the remainder from the truncated decimal form.

Unfortunately, since 29 is a prime number, I also do not see any way to simplify that.

6. Jul 12, 2012

### Travis_King

Yea the real problem that I see is most calculation software have their upper limit at around the 10^23 range...I know it was a big number, but I didn't think it was so large in my original post.

7. Jul 12, 2012

### Saitama

Thanks for the effort HallsofIvy, i will see if the question is correct by confirming it from my friend.

Btw, wolframalpha gives me this: http://www.wolframalpha.com/input/?i=remainder(25!/29)

8. Jul 12, 2012

### Travis_King

WolframAlpha gives the result as 5.

Calculate 25!/9
Truncate at the correct decimal place
subtract 25! by the truncated result
There ya go!

9. Jul 12, 2012

### Curious3141

By Wilson's Theorem,

28! = -1 (mod 29)

25!(26)(27)(28) = -1 (mod 29)

25!(-3)(-2)(-1) = -1(mod 29)

25! = 6^(-1) (mod 29) = 5 (mod 29).

The last step involved calculating the modular inverse of 6 (mod 29).

10. Jul 12, 2012

### Saitama

Never heard of it, will check that out.

I was afraid of this, i have never used the mod notation and i don't even know what that means. I think i will have to check that too. Thanks for the help Curious!

11. Jul 12, 2012

### Saitama

Seems like mod is related to remainder.

Can you tell me how did you replace 26,27 and 28 with -3,-2 and -1?

I see at wikipedia that the congruence sign is used instead of equality sign.

12. Jul 12, 2012

### Curious3141

You may replace all the equals signs with congruence signs, I was just typing fast.

26 = 29 - 3

When you take everything modulo 29, on the RHS, you get: 29 = 0 (mod 29), so you're left with:

26 = 0 + (-3) (mod 29) = -3 (mod 29)

The same applies for the others.

The most involved part is calculating the modular inverse of 6. For that, you can use any implementation of the Extended Euclidean Algorithm. I like the "magic box" method mentioned in wiki, it's very spinal and quick for small numbers.

13. Jul 12, 2012

### Infinitum

It is called modular arithmetic.

It basically involves getting a remainder when a given number is divided by a certain integer. So when you have,

$$a \equiv b (mod \ n)$$

a is the given number
b is the remainder
n is the divisor

There are really interesting relations using this, and you can find them online. If you are still interested, look up Chinese remainder theorem, Fermat's little theorem, Wilson's theorem(which Curious used), and Euler's theorem.

Edit : Seems I am late, but here is the post anyway.

What is $$26 \equiv x(mod 29)$$ And so on...

Take a look at this pdf file, too.
http://aleph.math.louisville.edu/teaching/2011SP-311/notes-110209.pdf

Do you see the property being used?

14. Jul 12, 2012

### Saitama

I don't know much (or nothing) about modular arithmetic, most of the stuff is going off my head. I don't get it when you say take "modulo" on RHS. For example, in an equation, if we perform any action like multiplication, division etc on LHS, we do it the same on RHS, i don't know about this modulo thing, can we do it on one side of the equation?

15. Jul 12, 2012

### Curious3141

You're doing it on both sides because the statement $a \equiv b \pmod n$ is defining a congruence class modulo n. It's saying that a and b are equivalent in some way, specifically that they leave the same remainder when divided by n.

I have to go to sleep now (past midnight here), but please read up on modular arithmetic in the meantime.

16. Jul 12, 2012

### Saitama

Thanks for the help Curious! Good night, i will be studying about modular arithmetic and post some questions.

@Infinitum: I am checking out the pdf file you linked to.

$26\equiv x\mod 29$ means $0\equiv(26-x)\mod29$, am i right here? How can i calculate x from here?

EDIT: Sorry that was a noob question. :tongue:

17. Jul 12, 2012

### Infinitum

That should be, $0\equiv(x-26)\mod29$

What remainder do you get when you divide 26 by 29? That's x.

18. Jul 12, 2012

### Saitama

Why my expression is wrong?
From my expression i can say that x=-3, because 26-(-3) mod 29=0.

19. Jul 12, 2012

### Infinitum

It isn't wrong. Saying the remainder is -3, as Curious explained in one of his above posts, is equivalent to saying that the remainder is 26. Its just intuitively easier to see a positive remainder over a negative one. Also, it comes with an advantage that you can see the numbers being 'subtracted' on both sides, just like in case of equality.

20. Jul 12, 2012

### Saitama

Okay, i get it. You asked me what's the remainder when you divide 26 by 29. Shouldn't that be 26? This modular arithmetic is completely new thing to me. I have never dealt with negative remainders.