1
$\begingroup$

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

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

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

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

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$

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.