1
$\begingroup$

How to prove that $31$ divides $28!+233$?

I have tried to use Wilson's theorem and the primes decomposition theorem, but I have not had success.

Thanks for your help

$\endgroup$

marked as duplicate by Bill Dubuque divisibility Apr 4 at 22:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You can use Wilson's theorem. Then you can calculate the multiplicative inverse modulo 31 of 29 and 30. $\endgroup$ – Cheerful Parsnip Apr 4 at 3:14
  • $\begingroup$ @CheerfulParsnip: after I posted my answer, I saw you had already commented the same idea. I still wonder why the problem has $233$ and not, say, $16$ $\endgroup$ – J. W. Tanner Apr 4 at 3:45
  • $\begingroup$ @J.W.Tanner I'm not sure if the choice of 233 has any significance here. $\endgroup$ – Cheerful Parsnip Apr 4 at 4:45
2
$\begingroup$

I’m sure that there are many ways of doing this. $$ 28!+233\equiv30!\cdot29^{-1}\cdot30^{-1}+233\equiv(-1)\cdot29^{-1}\cdot(-1)+233\equiv29^{-1}+233\pmod{31} $$ Now, $29^{-1}\equiv15\pmod{31}$ because $15\cdot29=435=434+1=1+14\cdot31\equiv1\pmod{31}$.

This tells you that $28!+233\equiv15+233\pmod{31}$, whereas $15+233=248=8\cdot31$, and that’s it.

$\endgroup$
5
$\begingroup$

By Wilson's theorem, $30!\equiv -1 \pmod {31}$.

$30\equiv-1 \pmod {31}$, so this means $29!\equiv1\pmod {31}.$

$29\equiv -2 \pmod {31},$ so this means $28!\equiv 1/-2 \equiv-1/2\equiv-1\times16\pmod {31}$.

Therefore $28!+233\equiv-16+233=217=31*7\equiv0\pmod{31}.$

$\endgroup$
  • $\begingroup$ This is better and clearer than my answer. $\endgroup$ – Lubin Apr 4 at 3:34
1
$\begingroup$

Wilson's Theorem is a good idea. So we know that $30!\equiv-1(\mod 31).$ So how could we use that here? Well, consider $$(28!+233)\equiv0(\mod 31)$$ $$\Updownarrow$$ $$(30*29)*(28+233)\equiv-1+30*29*233\equiv 0(\mod{31})$$ Now we just note that $$6539*31=202710=30*29*233-1,$$ so $$(30*29)*(28+233)\equiv-1+30*29*233\equiv 0(\mod{31}).$$

$\endgroup$
  • 1
    $\begingroup$ It is a bit easier to replace $30, 29, 233$ by $-1, -2, 16$: their residues modulo $31$. Then you don't have to encounter six-digit numbers. $\endgroup$ – Misha Lavrov Apr 4 at 3:24
  • $\begingroup$ @Misha Lavrov by hand you're right. Honestly, I just used a calculator. $\endgroup$ – Melody Apr 4 at 3:29
1
$\begingroup$

You can use wilson's theorem as in the other answer. I'll provide an alternative.

$$ 28!= \frac{30!}{29\cdot30}\equiv \frac{-1}{29\cdot-1}\equiv 29^{-1}\equiv 15\pmod{31}\text{, since }233\equiv 16\pmod{31}\text{, } 28!+233\equiv 0\pmod{31} $$

To find fast the inverse of 29, observe $29 = 31 - 2$, you want to find $31 - x$, so you solve $2x\equiv 1$ and $x=16$, and your number is $31 - 16 = 15$.

$\endgroup$
1
$\begingroup$

$$28!+233=\frac{30!}{30\cdot29}+31\cdot7+16\equiv\frac{-1}{-1\cdot(-2)}+16=16-\frac{1}{2}=\frac{31}{2}\equiv0.$$

$\endgroup$
  • $\begingroup$ I like this approach very much, too. $\endgroup$ – Lubin Apr 5 at 0:02
0
$\begingroup$

You can complete to Wilson's theorem: $$28!+233\equiv 28!+16\equiv 0\pmod{31} \iff \\ (28!+16)\cdot 29\cdot 30=30!+16\cdot (-2)\cdot (-1)\equiv 30!+1\equiv 0\pmod{31}\iff \\ 30!\equiv -1\pmod{31}.$$

$\endgroup$

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