Find Remainder of 25! Divided by 29: Help Appreciated

[Saitama]

Homework Statement

Find the remainder of \frac{25!}{29}

Homework Equations

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!

 

[Travis_King]

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

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

 

[Saitama]

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

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

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

 

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

 

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

 

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

 

[Saitama]

I believe Pranav-Arora is asking if there is a simpler way of calculating that since 25! 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.

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)

 

[Travis_King]

WolframAlpha gives the result as 5.

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

 

[Curious3141]

The answer is 5.

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

 

[Saitama]

By Wilson's Theorem,

Never heard of it, will check that out.

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

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!

 

[Saitama]

Seems like mod is related to remainder.

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

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

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.

 

[Curious3141]

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.

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.

 

[Infinitum]

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.

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.

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

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?

 

[Saitama]

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.

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?

 

[Curious3141]

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 about this modulo thing, can we do it on one side of the equation?

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.

 

[Saitama]

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

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.

 

[Infinitum]

@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?

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

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

 

[Saitama]

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

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

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

 

[Infinitum]

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

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.

 

[Saitama]

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.

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.

 

[Infinitum]

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.

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

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)

 

[Saitama]

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

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.

 

[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?

 

[Curious3141]

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?

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.

 

[Saitama]

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.

Okay, i will check the web for this stuff.

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.

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.

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.

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.

 

[Curious3141]

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.

Modular arithmetic needs to be read as part of elementary number theory. So I guess you could start with the basics there -

Prime and composite numbers,

The concept of gcd and lcm, and the relationship between gcd, lcm and the product of two numbers. The concept of coprimality/relative primality.

Then go on to Bezout's identity, which is a very simple Diophantine equation (read about this as well).

Then start with the basics of modular, or 'clock' arithmetic, which we've mostly covered.

You might want to explore Euclid's algorithm at this point.

Understand deeper concepts in modular arithmetic like the inverse, the calculation of which involves using Euclid's algorithm, and an understanding of Bezout's identity, coprimality, etc.

Now get started on Fermat's little Thorem and Wilson's Theorem.

Now read about Chinese Remainder Theorem and simultaneous congruences.

That should keep you occupied for a while.

 

[Saitama]

Thank you Curious, that will surely help me.

 

[ehild]

Pranav, A≡b(mod n) means that A =kn + b, where k is integer.

If n=5, for example, all numbers can be written as A=5k, 5k+1, 5k+2, 5k+3, 5k+4: Any number is either divisible by 5 or greater by 1,2,3,4, then a number divisible by 5. But also they can be 1, 2, 3, 4 less then a number divisible by 5. 7 is 2+5, but it is also 10-3. 7=5*1 +2 or 5*2-3.
Writing in the modular form 7=2(mod5) or 7=-3(mod5)

If you multiply two numbers X=5k+1 and Y=5l+4 for example,

XY=25kl + 5l + 20k +1 = 5t +4 (t is an integer).

In modular form: 1(mod5)*4(mod5)=4(mod5)=(-1)(mod5).

In the same way, (5k+2)(5l+3)=25kl +10l + 15k+ 6 =5r+1 (r is integer): 2(mod5)*3(mod5)=1(mod5)

If you write X=5k+1, Y = 5l-1, XY= 5t-1: 1(mod5)*(-1)mod(5)=-1(mod5).

If X=5k+2, Y=5k-2, XY=5r-4 = 5r'+1. 2(mod5)*(-2)mod(5)=-4(mod5) =1(mod5)

ehild

 

[Saitama]

Pranav, A≡b(mod n) means that A =kn + b, where k is integer.

If n=5, for example, all numbers can be written as A=5k, 5k+1, 5k+2, 5k+3, 5k+4: Any number is either divisible by 5 or greater by 1,2,3,4, then a number divisible by 5. But also they can be 1, 2, 3, 4 less then a number divisible by 5. 7 is 2+5, but it is also 10-3. 7=5*1 +2 or 5*2-3.
Writing in the modular form 7=2(mod5) or 7=-3(mod5)

If you multiply two numbers X=5k+1 and Y=5l+4 for example,

XY=25kl + 5l + 20k +1 = 5t +4 (t is an integer).

In modular form: 1(mod5)*4(mod5)=4(mod5)=(-1)(mod5).

In the same way, (5k+2)(5l+3)=25kl +10l + 15k+ 6 =5r+1 (r is integer): 2(mod5)*3(mod5)=1(mod5)

If you write X=5k+1, Y = 5l-1, XY= 5t-1: 1(mod5)*(-1)mod(5)=-1(mod5).

If X=5k+2, Y=5k-2, XY=5r-4 = 5r'+1. 2(mod5)*(-2)mod(5)=-4(mod5) =1(mod5)

ehild

Nicely explained, ehild! Thanks!

 

[ehild]

You can define addition and multiplication on the remainders. In case of mod5,

1+1=2, 2+2=4, 4+1=0, 4+2=1, 4+3=2, 4+4=3...

You can define zero (as x+0=x) and negative. -x is defined as the element which added to x, gives 0. This way (4) (mod5)+1(mod5)=0 →(-1)(mod5)≡4(mod)5.

You can define unit and multiplication. 1*x=x

2*2=4 (or -1), 2*3=1, 2*4=3,(or-2) 3*3=4,(or-1) 3*4=2, 4*4=1.
You can also define reciprocal of x: x^-1: x*x^-1=1

1^-1=1 as 1*1=1
2^-1=3 as 2*3=1
3^-1=2 as 3*2=1
4^-1=4 as 4*4=1

Each element has a unique reciprocal, except zero. The reciprocal of both 1 and (-1) are themselves.

The remainders of a prime are 0, 1, 2,..., p-1. Except zero, all element have reciprocals. So p-1! can be grouped as the product of the elements with its reciprocals except the first and last ones. If p=5 5!=(1) (2*3)*(4)=1*1*(4)≡(-1)

For p=7, 2*4=1(mod7), 3*5=1, 6*6=1. So 2^-1=4, 3^-1=5, 4^-1=2, 5^-1=3, 6^-1=6 (or -1)
6!=(1)*(2*4)*(3*5)*(6) = 1*1*1*(-1)

For p prime, p-1 is even. The elements different from 1 and p-1 can be paired so as their product is 1. So p-1!=(p-1) (modp) that is (-1)(modp). (Wilson's Theorem).

28!=-1(mod29)

28!=25!*26*27*28.

28=(-1)(mod29), 27=(-2)(mod29), 26=(-3)(mod29)

28!=25!*(-1)*(-2)*(-3)=-1: 25!=6^-1 (mod29)
6^-1=5 (mod29) as 5*6=30=1+29
Therefore 25!=5(mod29).

ehild

 

[Curious3141]

You can define addition and multiplication on the remainders. In case of mod5,

1+1=2, 2+2=4, 4+1=0, 4+2=1, 4+3=2, 4+4=3...

You can define zero (as x+0=x) and negative. -x is defined as the element which added to x, gives 0. This way (4) (mod5)+1(mod5)=0 →(-1)(mod5)≡4(mod)5.

You can define unit and multiplication. 1*x=x

2*2=4 (or -1), 2*3=1, 2*4=3,(or-2) 3*3=4,(or-1) 3*4=2, 4*4=1.
You can also define reciprocal of x: x^-1: x*x^-1=1

1^-1=1 as 1*1=1
2^-1=3 as 2*3=1
3^-1=2 as 3*2=1
4^-1=4 as 4*4=1

Each element has a unique reciprocal, except zero. The reciprocal of both 1 and (-1) are themselves.

The remainders of a prime are 0, 1, 2,..., p-1. Except zero, all element have reciprocals. So p-1! can be grouped as the product of the elements with its reciprocals except the first and last ones. If p=5 5!=(1) (2*3)*(4)=1*1*(4)≡(-1)

For p=7, 2*4=1(mod7), 3*5=1, 6*6=1. So 2^-1=4, 3^-1=5, 4^-1=2, 5^-1=3, 6^-1=6 (or -1)
6!=(1)*(2*4)*(3*5)*(6) = 1*1*1*(-1)

For p prime, p-1 is even. The elements different from 1 and p-1 can be paired so as their product is 1. So p-1!=(p-1) (modp) that is (-1)(modp). (Wilson's Theorem).

28!=-1(mod29)

28!=25!*26*27*28.

28=(-1)(mod29), 27=(-2)(mod29), 26=(-3)(mod29)

28!=25!*(-1)*(-2)*(-3)=-1: 25!=6^-1 (mod29)
6^-1=5 (mod29) as 5*6=30=1+29
Therefore 25!=5(mod29).

ehild

Very complete, and very patient of you! I wish I had the time/patience to type all that out.

 

[ehild]

But I understood the solution of the original problem from your explanation .

ehild

 

[Curious3141]

But I understood the solution of the original problem from your explanation .

ehild

But honestly, I believe you're the far better teacher.

 

[Saitama]

Thanks once again ehild!

28!=25!*(-1)*(-2)*(-3)=-1: 25!=6^-1 (mod29)
6^-1=5 (mod29) as 5*6=30=1+29
Therefore 25!=5(mod29).

ehild

I still don't understand how you get
6^-1=5 (mod29) and what does this mean "5*6=30=1+29 "?

If we suppose, x is the number we need to find here in this: 6^-1=x (mod 29), how should i go on finding that?

 

[ehild]

The remainders with respect to a (prime) number n constitute a finite "field" with operations like addition and multiplication. Both have inverse: the inverse of addition is the negative remainder. I denoted the inverse of multiplication as x^-1. It is not the number 1/x, but a symbol for the element which multiplied by x results 1:

x^-1 * x=1 in modular arithmetic.

Curious certainly knows the official notation for the reciprocal in modular arithmetic.

Of course, 6^-1 is also a remainder, one of those you get when dividing a number by 29. We want to find it.
Let's go back to the real numbers. What are those numbers which multiplied by a number of form 29k+6 gives 1 more than a number divisible by 29? ( (29k+6)*(29l+a)=29r+1 ) You know that a<29 and it is an integer. You can take k and l equal to zero. So 6a=29r+1. 29r+1 has to be divisible by 6. If r=1, 29+1=30=6a, so a=5. You can try other r-s, but none is appropriate. There is no other value for "a" than 5.
So 6^-1 = 5 (mod29) .

Try it with 35*63=2205, for example. ( 35=29+6, 63=2*29+5.) Dividing by 29 , the remainder is 1. Or 325*208=67600=2331*29+1.

ehild

 

[Curious3141]

Thanks once again ehild!

I still don't understand how you get
6^-1=5 (mod29) and what does this mean "5*6=30=1+29 "?

That's based on the definition of multiplicative modular inverse. Remember that if ax \equiv 1 \pmod n such that 0 &lt; x &lt; n, then x is defined as the multiplicative modular inverse of a modulo n. x is only defined if (a,n) = 1, which is a fancy way of saying the greatest common divisor of a and n is 1, which is another way of saying that a and n are coprime.

The notation for the modular inverse is a^{-1}, so here you can write: x \equiv a^{-1} \pmod n.

So, in this particular case, 5 \equiv 6^{-1} \pmod {29} because (5)(6) = 30 \equiv 1 \pmod {29}, which is what ehild was highlighting.

Only two numbers give "self inverses": 1 and (n-1). This is easy to see if you solve a \equiv a^{-1} \pmod n. Multiply both sides by a (remember this is OK, because a and n are coprime, therefore you are not multiplying by zero). So you get: a^2 \equiv 1 \pmod n, which has solutions of a \equiv \pm 1 \pmod n, so a can be 1 or (n-1).

If we suppose, x is the number we need to find here in this: 6^-1=x (mod 29), how should i go on finding that?

The method to actually go about finding the inverse (when it's not trivial as discussed above) is called Euclid's algorithm. It can be implemented simply by using the "magic box" method mentioned in the wiki article on the first page. There's a cool online implementation of this algorithm that shows the steps, and here it is: http://www.cs.princeton.edu/~dsri/modular-inversion.html