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$$
Answer
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$.
Added explanation:
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$.
No comments:
Post a Comment