Find Remainder of 25! Divided by 29: Help Appreciated

[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