Wednesday, December 16, 2015

elementary number theory - $3$ never divides $n^2+1$


Problem: Is it true that $3$ never divides $n^2+1$ for every positive integer $n$? Explain.


Explanation: If $n$ is odd, then $n^2+1$ is even. Hence $3$ never divides $n^2+1$, when $n$ is odd.



If $n$ is even, then $n^2+1$ is odd. So $3$ could divide $n^2+1$.


And that is where I am stuck. I try to plug in numbers for $n$ but I want a more general form of showing that $3$ can't divide $n^2+1$ when $n$ is even.


Answer



Instead of considering whether $n$ is even or odd, consider the remainder when $n$ is divided by $3$; as an example, if the remainder is $1$, we have $$n = 3k + 1 \implies n^2 + 1 = 9k^2 + 6k + 2$$


which is not divisible by $3$. There are two more cases.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...