Find $2^{1008} \mod 2017$

From Fermat's we can find that $2^{2016} \equiv 1 \mod 2017$.
But now we cant say that $2^{1008} \equiv 1 \mod 2017$. It can be $-1$ too. But how to prove that it is equal to $1$?


One way would be to find $2^{1008} \pmod{2017}$ using the binary expansion of $1008 = 1111110000_{(2)}$.

A different method uses quadratic residues: Since 2017 is a prime $\equiv 1\pmod{8}$, 2 is a quadratic residue mod 2017. (see https://en.wikipedia.org/wiki/Quadratic_residue )

Then there exist values $r$ (more precisely, 986 and 1031) such that $r^2 \equiv 2 \pmod{2017}$, which implies that $2^{1008} \equiv r^{2016} \equiv 1\pmod{2017}$.


If you have Quadratic Reciprocity at your disposal, then Catalin Zara's answer is the way to go. If not, a little experimentation (and a bit of luck) leads to the following:


The first step is based on the theorem that $\left(-1\over p\right)=1$ for $p\equiv1$ mod $4$. As in Zara's answer, the final conclusion for $2^{1008}$ follows from the theorem that $r^{(p-1)/2}\equiv1$ mod $p$ when $\left(r\over p\right)=1$.

Added later: A bit more experimentation gives a simpler evaluation, using the factorizations $8=2\cdot4$ and $2025=45\cdot45$:




Thus, $$2^{1008}-1\equiv986^{2016}-1\equiv0$$

  • $\begingroup$ Where did that come from? $\endgroup$ – lhf Feb 13 '17 at 23:04
  • $\begingroup$ @lhf Do you understand what do you ask? $\endgroup$ – Michael Rozenberg Feb 14 '17 at 2:30
  • $\begingroup$ @MichaelRozenberg >:( Where did that come from :O :| $\endgroup$ – 0123456789101112 Feb 15 '17 at 4:45
  • $\begingroup$ @12345678 I my proof there are three steps: 1. $986^2-2=2017\cdot482$; 2. $2^{1008}-1\equiv986^{2016}-1$ and $986^{2016}-1\equiv0$. About which of them do you ask? $\endgroup$ – Michael Rozenberg Feb 15 '17 at 4:51

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.