3
$\begingroup$

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

$\endgroup$
9
$\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$
  • $\begingroup$ @yunone: Thanks, after seeing the answer I feel like I need to take a break :(. $\endgroup$ – Chan Feb 26 '11 at 7:50
  • $\begingroup$ @Chan, no problem. Working too long can be hard on anyone. Things will probably look clearer in the morning. $\endgroup$ – yunone Feb 26 '11 at 7:55
  • $\begingroup$ @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. $\endgroup$ – Chan Feb 26 '11 at 7:57
  • $\begingroup$ @Chan, I'm not sure how you did your calculation. According to wolframalpha $-5!25!+1$ is indeed divisible by $31$. $\endgroup$ – yunone Feb 26 '11 at 8:03
  • $\begingroup$ @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. $\endgroup$ – Chan Feb 26 '11 at 8:10
1
$\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$
  • $\begingroup$ Thanks! I'm really weak when thinking in term of modulo. $\endgroup$ – Chan Feb 26 '11 at 7:50
0
$\begingroup$

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$

$\endgroup$
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.