# Multiplicative inverse for $2^{1000}$ mod $2017$

We know that 2017 is a prime number. I'm trying to find the multiplicative inverse for $2^{1000}$ mod $2017$.

By the Fermat theorem, we have $2^{2016}\equiv 1\pmod {2017}$. It follows that $2^{1000}\cdot2^{1016}\equiv1\pmod {2017}$. Thus, $2^{1016}$ is the multiplicative inverse of $2^{1000}$ mod $2016$.

Is my reasoning right?

your reasoning is fine... but I thought I would point something out...

$2^{1008} \equiv \pm 1 \pmod{2017}$ because $(2^{1008})^2 \equiv 1 \pmod{2017}$

So, $2^{1016} \equiv \pm 2^8 \pmod{2017}$

And as it turns out $2^{1016} \equiv 256 \pmod{2017}$

• so 256 is also an multiplicative inverse? – user42912 Jan 4 '17 at 23:11
• Indeed it is... – Doug M Jan 4 '17 at 23:13

You can do it by finding modular multiplicative inverse by Euler's criterion:

$$2^{1000}\equiv 1757 \pmod{2017}$$

$$1757^{\varphi(2017)-1} \equiv 256 \pmod{2017}$$

$$1757\cdot 256 \equiv 1 \pmod{2017}$$

• Downvoter try to leave a comment so I can know your motivation... – kub0x Jan 5 '17 at 17:57