Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 7 down vote accepted

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}$.

share|improve this answer
    
@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
show 3 more comments

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.

share|improve this answer
    
Thanks! I'm really weak when thinking in term of modulo. –  Chan Feb 26 '11 at 7:50
add comment

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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