Show that if $p$ is a prime such that $p|(2^{64}+1)$ then $p \equiv 1 $ (mod 128) 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. 
 A: Hint: Since $p \mid 2^{64} + 1$ you have $2^{64} \equiv -1 \bmod p$ and so $2^{128} \equiv 1 \bmod p$.
A: 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}$.

A: There are only two such primes, namely $274177 = 1 + 2142\cdot 128$ and $67280421310721 = 1 + 52562891490\cdot 128$.
A: 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.
