Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Note that $2016\equiv -1 \mod 2017$. –  Dietrich Burde Mar 30 at 15:34
    
Wow, didn't realize how close I was.. thanks guys! –  Jonathan Mckibbin Mar 30 at 15:42

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
By the way, if I'm not mistaken the above actually proves the theorem. I read this somewhere. Don't remember where. –  Sabyasachi Mar 30 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$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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