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

21. Jul 12, 2012

### Infinitum

Yes, it is 26, and also -3, or any other number that gives the same remainder when divided by 29. That is explained in the introductory paragraph of the pdf

Its a bit less intuitive for negative numbers, but as Curious explained above...

22. Jul 12, 2012

### Saitama

I read that but i could not understand, i think i need to get used to with the negative remainders. Do you have any good link for the theorems you just mentioned, wiki seems to show that in a lot of detail.

23. Jul 12, 2012

### Saitama

Is there any good link to study how to find the modular inverse?

Do you have any good book suggestions from where i can study modular arithmetic?

24. Jul 12, 2012

### Curious3141

With regard to number theory, I'm almost completely self-taught. It's one of those things that school doesn't do justice to, which is ironic, since whole numbers are the first mathematical concepts to be taught to schoolchildren. The problem is that schools are rushing to introduce rational numbers, then real numbers, etc. etc. The other problem is that number theory can get quite abstract and difficult to understand even a little way in.

I've read at least one book on Number Theory, but I can tell you that most of them (including the one(s) that I've read) are major drags. The format of proposition/lemma followed by proofs that make you jump all over the book, or even outside the book to look up other stuff - is just not conducive to sustaining the interest of a keen, but otherwise busy, amateur.

So I recommend looking up this stuff on the web. You've already got a reasonably good resource in Wiki. Wolfram Mathworld is an even better, albeit more technical, resource. There are plenty of other resources, like online lecture notes, etc.

Just to correct a small misconception you may have, $a \equiv b \pmod n$ does not necessarily mean that b is the remainder of a when a is divided by n. For starters, b may be greater than a, and $a \equiv b \pmod n$ and $b \equiv a \pmod n$ are equally valid ways of writing it.

What that statement says is that, to get from a to b (or vice versa), you need to add or subtract an integer multiple of n. It's that simple. You can also express the relationship as $a = kn + b$, where $k \in \mathbb{Z}$. When you start doing modular arithmetic, you'll probably find yourself constantly going back to this "simplistic" notation to convince yourself of something - nothing wrong with that. When you get used to writing mod this and mod that, you won't need to go back to that simple algebraic statement anymore, or at least, less frequently.

Remember that the remainder is defined as a non-negative residue that's strictly smaller than the divisor. So b is the remainder iff (if and only if) b is the unique integer such that $0 \leq b < n$ and $a \equiv b \pmod n$. Get that part? The modulo equivalence is actually a whole lot more powerful than just finding remainders, and that's why it can handle negative numbers, and numbers greater than the divisor, etc.

The modular multiplicative inverse is a tricky concept, and you might need to get familiar with all this stuff before you tackle it. Basically, the modular inverse of a (mod n) is denoted by $a^ {-1} \pmod n$ and it's the smallest positive integer x strictly less than n such that $ax \equiv 1 \pmod n$. See the parallel to the normal multiplicative inverse (reciprocal) there? The modular inverse exists iff gcd(a,n) = 1, which is a condition called coprimality or relative primality between a and n.

I hope you see that there's a lot of ground to cover here, which is why I recommended that you start by looking this stuff online to cover the basics.

25. Jul 12, 2012

### Saitama

Okay, i will check the web for this stuff.

I know somewhat about this. I was introduced to modular arithmetic previous year by a member from this place but i don't know why i could not understand it.

Thanks for the explanation!

Could you give me a list of topics i should start with (in an order, from basic stuff to theorems)? I will be doing modular arithmetic on my own, i would need a way to start, i don't want to get confused by lurking from pages to pages on Wikipedia. A list of topics would probably help.