Need help to find remainder when $5!25!$ is divided by $31$?

I'm really confused about congruence. I tried hard, but I kept failing :(

$$30! \equiv -1 \pmod{31} \text{ by Wilson's Theorem}$$ $$\Longleftrightarrow 30.29.28.27.26.25! \equiv -1 \pmod{31}$$ $$\Longleftrightarrow (-1).15.10.(-8).6.25! \equiv -1 \pmod{31}$$ $$\Longleftrightarrow 15.4.5!.25! \equiv -1 \pmod{31}$$ $$\Longleftrightarrow 60.5!.25! \equiv -1 \pmod{31}$$ $$\Longleftrightarrow 15.5!.25! \equiv -1 \pmod{31}$$

And I was stuck here :( ? Furthermore, I have to use computer to find a pair of solution of the Diophantine equation $ax + 31y = 1$ for each number: $30, 29, 28, 27, 26 ...$ I wonder is there an easier way to do this? Because I think this way is very time consuming. Any idea?

Thanks,
Chan

-

3 Answers

So by Wilson's Theorem, you have $$30\cdot 29\cdot 28\cdot 27\cdot 26\cdot 25!\equiv -1\pmod{31}.$$ But notice this implies $$(-1)(-2)(-3)(-4)(-5)25!\equiv (-1)^5 5!25!\equiv -1\pmod{31},$$ since $30\equiv -1\pmod{31}$, $29\equiv -2\pmod{31}$,$\dots$, and $26\equiv -5\pmod{31}$.

-
@yunone: Thanks, after seeing the answer I feel like I need to take a break :(. –  Chan Feb 26 '11 at 7:50
@Chan, no problem. Working too long can be hard on anyone. Things will probably look clearer in the morning. –  yunone Feb 26 '11 at 7:55
@yunone: From your equation: $(-1)^{5} = -1$. So $-5!25! + 1$ is divisible by 31, but this is not true. Can you explain this? Sorry if I misunderstood your instruction. –  Chan Feb 26 '11 at 7:57
@Chan, I'm not sure how you did your calculation. According to wolframalpha $-5!25!+1$ is indeed divisible by $31$. –  yunone Feb 26 '11 at 8:03
@yunone: I really apologized for being careless, since my calculator mode was on faction mode, so I saw the quotient as fraction with power of 10. –  Chan Feb 26 '11 at 8:10

If you are looking for $x$ such that $15x = 1 \mod 31$, notice that $15 \times 2 = 30 = -1 \mod 31$

Hence $15 \times (-2) = 1 \mod 31$.

But, as yunone's answer shows, you have a mistake somewhere.

-
Thanks! I'm really weak when thinking in term of modulo. –  Chan Feb 26 '11 at 7:50

As I said in your prior question, Wilson's theorem yields the reflection formula

$$\rm (p-1-k)\:!\ \equiv\ \frac{(-1)^{k+1}}{k!}\ \ (mod\ p),\ \ for\ p\ prime$$

Hence $\rm\displaystyle\ 25!\equiv \frac{1}{5!}\ (mod\ 31)\:.\:$ But $\rm\ 5!\equiv 4\ (5\cdot3\cdot2)\equiv -4,\:\:$ and $\rm\ 4\cdot 8\equiv 1\ \Rightarrow\ 1/4\equiv 8\ (mod\ 31)\:.\:$

Therefore we conclude that $\rm\ 1/5!\equiv -1/4 \equiv -8\ (mod\ 31)\:.\$ Indeed $\rm -8\cdot 5! = 1 - 31^2$

-