# Find the smallest positive integer x such that 2015! ≡ x (mod 2017)

Q. The next year that is a prime is 2017. Find the smallest positive integer x such that 2015! ≡ x (mod 2017).

So, this is what I have;

By Wilson’s theorem, (2017-1)! ≡ -1 (mod 2017) ⇒ 2016! ≡ -1 (mod 2017) ⇒ 2016∙2015! ≡ -1 (mod 2017) ⇒

not sure how to do the modular arithmetic to have just 2015! on the left side..

• Note that $2016\equiv -1 \mod 2017$. – Dietrich Burde Mar 30 '14 at 15:34
• Wow, didn't realize how close I was.. thanks guys! – User011123521 Mar 30 '14 at 15:42

Hint:

$2016$ is relatively prime to $2017$

If, $c$ is relatively prime to $p$, then,

$$ac\equiv bc\pmod{p}\iff a\equiv b\pmod{p}$$

Also, $$2016\equiv -1\pmod{2017}$$

Also, if I may lengthen this on purpose, then let's do this without Wilson's Theorem.

Consider $2 \le a\le 2015$. To each such $a$, we associate it's unique inverse $\overline a$, i.e, $a\overline a\equiv1\pmod{2017}$. Note that $a\ne \overline a$, because then $a^2\equiv 1\pmod{p}$ which would mean $a\equiv \pm 1\pmod{p}$ which is not possible for the $a$ in consideration. Thus in multiplying all $a\in \{2,3,\cdots,2015\}$ we pair them with their inverses, and the net product is $1$.

$$2015!\equiv 1\pmod{2017}$$

QED

• By the way, if I'm not mistaken the above actually proves the theorem. I read this somewhere. Don't remember where. – Guy Mar 30 '14 at 15:46

As $2017$ is prime, using Wilson's Theorem $$2016!\equiv-1\pmod{2017}$$

$$\iff 2015!\cdot 2016\equiv-1\pmod{2017}$$

$$\iff 2015!\cdot (-1)\equiv-1\pmod{2017}\text{ as }2016\equiv-1\pmod{2017}$$

So, $\cdots$

Your solution is almost done. Notice that $2016 \equiv -1 \text{ }mod(2017)$ so $$2015!(-1)\equiv (-1) mod (2017)\implies 2015!\equiv 1$$