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
4 Answers
$\begingroup$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}$.
$\endgroup$ 8 $\begingroup$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.
$\endgroup$ 1 $\begingroup$I know this has already been answered using Wilson's but I'd like to be a little more explicit with the answer. I'm sure @Chan already has this down pat 6 years ago...
30! = 30*29*28*27*26*25!
30 is congruent to -1 mod 31
29 is congruent to -2 mod 31
28 is congruent to -3 mod 31
27 is congruent to -4 mod 31
26 is congruent to -5 mod 31
Now notice that 30! is congruent to -1 (mod p)
Then 30*29*28*27*26*25! is congruent to -1 (mod p)
But then taking the inverses, we have that -1*-2*-3*-4*-5*25! is congruent to -1 (mod p).
This is possible because for a congruent to b (mod p), b congruent to a (mod p). So 30*29*28*27*26*25! is congruent to -1*-2*-3*-4*-5*25! is congruent to -1 (mod p)
simplifying the left hand side of the equation, we get, (-1^5) * 5! * 25!
So (-1^5) * 5! * 25! is congruent to (-1 mod p)
We're almost there, since we need 5! * 25!, not 5! * 25! * -1
dividing each side by -1, we have that 5! * 25! is congruent to 1 (mod p)
From this, it is obvious the remainder is 1.
$\endgroup$ $\begingroup$As I noted 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 we deduce $\bmod 31\!:\,\ 25!\equiv \dfrac{1}{\color{#c00}5!}\equiv\dfrac{32}{\color{#c00}{-4}}\equiv -8,\, $ by $\ \color{#c00}{5!}\equiv 4\ (5\cdot3\cdot2)\equiv \color{#c00}{4(-1)}$
$\endgroup$
