Find a prime factor greater than 3 of the following integers:
(a) $2^6 + 1$
(b) $2^{14} + 1$
(c) $2^{15} - 1$
(d) $2^{20} - 1$
(e) $2^{114} + 1$
(f) $2^{504} - 1$
We'll make use of Proposition (4.19) which says that if $p= 2n + 1$ is prime, then
- $p \equiv \pm 1 \pmod 8 \implies p \mid (2^n− 1)$
- $p \equiv \pm 3 \pmod 8 \implies p \mid (2^n + 1)$
(a) We have $n=6$, and $p=2n+1= 13$ is prime, and also $13 \equiv -3 \pmod 8$.
By Proposition (4.19) we conclude $13 \mid 2^6 + 1$.
(b) We have $n=14$, and $p=2n+1= 29$ is prime, and also $29 \equiv -3 \pmod 8$.
By Proposition (4.19) we conclude $13 \mid 2^{14} + 1$.
(c) We have $n=15$, and $p=2n+1= 31$ is prime, and also $31 \equiv -1 \pmod 8$.
By Proposition (4.19) we conclude $31 \mid 2^{15} - 1$.
(d) We have $n=20$, and $p=2n+1= 41$ is prime, and also $41 \equiv +1 \pmod 8$.
By Proposition (4.19) we conclude $41 \mid 2^{20} - 1$.
(e) We have $n=114$, and $p=2n+1= 229$ is prime, and also $229 \equiv -3 \pmod 8$.
By Proposition (4.19) we conclude $229 \mid 2^{114} + 1$.
(f) We have $n=504$, and $p=2n+1= 1009$ is prime, and also $1009 \equiv +1 \pmod 8$.
By Proposition (4.19) we conclude $1009 \mid 2^{504} - 1$.