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$

1 Answer 1

3
$\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$
1
  • $\begingroup$ Got it and thank you for providing this alternative solution. (+1). $\endgroup$
    – vbm
    Apr 16, 2018 at 21:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .