Problem 3

Determine all integers

n>1

such that

(2^n+1)/n^2

is an integer.

Step 4 of 4: Exclude every second prime factor

Previous step Next step

n=3t,\quad q\mid t,\quad q>3\Longrightarrow w\mid n,\quad w<q,\quad w\in\{1,3\}

Detailed analysis

If $n>3$ , write $n=3t$ and let $q$ be the smallest prime divisor of $t$ , so $q>3$ . Repeating the exponent argument modulo $q$ gives a least $w$ with $2^w\equiv-1\pmod q$ , where $w$ divides $n$ and is less than $q$ . Since 3 occurs only once in $n$ , $w$ is 1 or 3; then $q$ divides 3 or $q\mid(2^3+1)=9$ , contradicting $q>3$ . Finally $n=3$ works because $(2^3+1)/3^2=1$ .