# $31$ divides $28!+233$? [duplicate]

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.

## marked as duplicate by Bill Dubuque divisibility StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 4 at 22:38

• You can use Wilson's theorem. Then you can calculate the multiplicative inverse modulo 31 of 29 and 30. – Cheerful Parsnip Apr 4 at 3:14
• @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$ – J. W. Tanner Apr 4 at 3:45
• @J.W.Tanner I'm not sure if the choice of 233 has any significance here. – Cheerful Parsnip Apr 4 at 4:45

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.

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

• This is better and clearer than my answer. – Lubin Apr 4 at 3:34

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

• 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. – Misha Lavrov Apr 4 at 3:24
• @Misha Lavrov by hand you're right. Honestly, I just used a calculator. – Melody Apr 4 at 3:29

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

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

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

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