# If $a(n)=n^2+1$ then $\gcd(a_n,2^{d(a_n)})=1\text{ or }2$?

Let $n\in\mathbf{N}$. I write $a_n=n^2+1$ and let $d(a_n)$ count the number of divisors of $a_n$. Set $$\Phi_n=\gcd\left(a_n,2^{d\left(a_n\right)}\right)$$ I would like to show and I believe it to be true that

$$\Phi_n = \begin{cases} 1, & \text{if n is even} \\[2ex] 2, & \text{if n is odd} \end{cases}$$

My gut instinct is two beak it down by parity and then use Euclid's lemma. But I am not sure how to use Euclid's lemma.

To see a working example consider $n=15$. Then $a_n=226$, $d(a_n)=4$ and $$\text{ }\Phi_n=\gcd(226,2^{4})=\gcd(226,16)=2$$

Note that $2^{d(a_n)}$ can only be divisible by $1$ and powers of $2$.

If $n$ is even then $n^2+1$ is odd and in that case $\gcd=1$.

If $n$ is odd, then $n^2+1 \equiv 2 \pmod{4}$. Thus $n$ is not divisible by $4$, hence the $\gcd=2$.

Using the division algorithm, we can write any integer $n=4k+r$, where $r \in \{0,1,2,3\}$. So when $n$ is odd, then it can only be of the form $4k+1$ or $4k+3$. Now consider the case when $n=4k+1$, then $$n^2+1=(4k+1)^2+1=16k^2+8k+2=4(\text{some integer})+2.$$ Likewise when $n=4k+3$,we have $$n^2+1=(4k+3)^2+1=16k^2+24k+8+2=4(\text{some integer})+2.$$
This means $n^2+1$ will always leave a remainder of $2$, when divided by $4$.
• Could you walk me through the odd case? I am not following it - in particular considering $n^2+1$ modulo $4$? – Antonio Hernandez Maquivar Dec 19 '16 at 19:57
• If $n$ is odd, then $n^2\equiv 1\pmod 4$, so $n^2+1\equiv 2\pmod 4$. – Xam Dec 19 '16 at 20:02