Show that if $p$ is a prime such that $p|(2^{64}+1)$ then $p \equiv 1 $ (mod 128)

Question

I'm not sure if I'm on the right track with this problem. So far I've said: $2^{64} = (2^{32})^2 \equiv -1$ (mod p). Then by Fermat's two square theorem $p = 2$ or $p \equiv 1$ (mod 4). We know $p \not = 2$ because $p|(2^{64}+1)$. Then $p \equiv 1$ (mod 4). From here I'm unsure on how to proceed.

Answer 1

Hint: Since $p \mid 2^{64} + 1$ you have $2^{64} \equiv -1 \bmod p$ and so $2^{128} \equiv 1 \bmod p$.

Answer 2

Edit: I misread and thought you wrote $p|2^{2^{64}}+1$. The result happens to hold as well, and it is actually the number Euler was trying to factor when he proved the theorem below.

---

Hint: You are on the right track since what you need is a generalization of Fermat's two-square theorem, due to Euler who used it to prove that not all Fermat's numbers are primes.

Theorem (Euler). For any coprime integers $a$ and $b$ with $a$ even, and any integer $n$, the prime factors of the sum $$a^{2^n}+b^{2^n}$$ will all be congruent to $1\bmod2^{n+1}$.

Answer 3

There are only two such primes, namely $274177 = 1 + 2142\cdot 128$ and $67280421310721 = 1 + 52562891490\cdot 128$.

Answer 4

Theorem: if $a^k\equiv 1\pmod{m}$, then $\text{ord}_m(a)\mid k$.

Proof: for contradiction, let $k=\text{ord}_m(a)h+r$, where $0<r<\text{ord}_m(a)$. But then $$1\equiv a^k\equiv a^{\text{ord}_m(a)h+r}\equiv$$

$$\equiv \left(a^{\text{ord}_m(a)}\right)^h\cdot a^r\equiv $$

$$\equiv 1^h\cdot a^r\equiv a^r\pmod{m},$$

contradiction because $0<r<\text{ord}_m(a)$ by the definition of multiplicative order.

You have $p\mid 2^{64}+1$, so $p$ is odd and $2^{64}\equiv -1\pmod{p}$, so $2^{2^6}\equiv -1\pmod{p}$, so also $2^{2^7}\equiv 1\pmod{p}$, so $\text{ord}_p(2)\mid 2^7$, also $\text{ord}_p(2)\nmid 2^6$ because $1\not\equiv -1\pmod{p}$, so $\text{ord}_p(2)=2^7$. Now use Fermat's little theorem.