1
$\begingroup$

Particularly, I want to prove $18!+1\equiv 0\pmod {23}$ so I wish to know if determining inverse of some numbers lead me to the proof correctly.

Give problem asks to Prove that $18!+1\equiv 0\pmod {437}$

$437$ is not a prime number but its factors $19$ and $23$ are prime.

Therefore using (in case of prime numbers only) Wilson's Theorem it can be shown that $18!+1\equiv 0\pmod {19}$.

To Prove $18!+1\equiv 0\pmod {23}$, we follow Wilson's theorem

$$(23-1)!\equiv -1\pmod{23}\\\Longrightarrow 21!\equiv 1\pmod{23},\space \gcd(22,23)=1 \to (I)$$.

I have determined inverses of $21,20,19$.

$$21x\equiv1\pmod{23} \to (i)\\20x\equiv1\pmod{23} \to (ii)\\19x\equiv1\pmod{23} \to (iii)$$ From $(i)$ $$\gcd (21,23)=1,\\23=21.1+2\\21=2.10+1\\\therefore 1=21-2.10\\=21-(23-21.1).10\\=21.11+23.(-10)$$

So from $(i), (ii), (iii)$ we have $11$ is the inverse of $21$, $(-8)$ is the inverse of $20$ and $(-6)$ is the inverse of $19$ and applying that in $(I)$ we get $$21!\equiv 1\pmod{23}\\\Longrightarrow 21.11.(20!)\equiv 11\pmod{23}\\\Longrightarrow 20!\equiv 11\pmod{23}\\\Longrightarrow 20.(-8).(19!)\equiv 11.(-8)\pmod{23}\\\Longrightarrow 19!\equiv 11.(-8)\pmod{23}\\\Longrightarrow 19.(-6).(18!)\equiv 11.(-8).(-6)\pmod{23}\\\Longrightarrow 18!\equiv 11.(-8).(-6)\pmod{23}\\\Longrightarrow 18!\equiv 11.48\pmod{23}\\\Longrightarrow 18!\equiv 11.2\pmod{23}\\\Longrightarrow 18!\equiv 22\pmod{23}\\\Longrightarrow 18!\equiv -1\pmod{23}\\\Longrightarrow 18!+1\equiv 0\pmod{23}$$

If this approach is correct then I can conclude that $18!+1\equiv 0\pmod{437}$. Any help is precious for learning and greatly appreciated. Any alternative quick method to solve this problem is also valuable.

$\endgroup$
2
$\begingroup$

Probably correct, but way too long! 🙂

You have $18!+1\equiv0\pmod{437}$ if and only if \begin{cases} 18!+1\equiv0\pmod{19} \\[4px] 18!+1\equiv0\pmod{23} \end{cases} The top relation is satisfied because of Wilson’s theorem. By the same theorem, $$ 22!+1\equiv0\pmod{23} $$ which means $$ 22\cdot21\cdot20\cdot19\cdot 18!\equiv-1\pmod{23} $$ On the other hand, $22\cdot21\cdot20\cdot19\equiv(-1)(-2)(-3)(-4)\equiv24\equiv1\pmod{23}$

$\endgroup$
  • $\begingroup$ Got it and thank you for providing this alternative solution. (+1). $\endgroup$ – thevbm Apr 16 '18 at 21:22

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.