Find Remainder of 25! Divided by 29: Help Appreciated

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