12
$\begingroup$

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.

$\endgroup$
  • 12
    $\begingroup$ An even number may or may not be divisible by $3$. For example, $6$ is even and divisible by $3$. $\endgroup$ – Michael Albanese Dec 28 '13 at 4:27
  • 1
    $\begingroup$ In a similar manner, prove that $5$ never divides $n^2+2$ and $n^2+3$. $\endgroup$ – Lucian Dec 28 '13 at 5:29

10 Answers 10

26
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

Hint: What are the only squares modulo $3$? Put another way, look at the expression $n^{2}+1$ modulo $3$. What is true of $n^{2} \pmod 3$ for any $n \in \mathbb{N}$?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But there are three results. that $n^2$ is congruent to 0,1,2 $\endgroup$ – Username Unknown Dec 28 '13 at 4:29
  • $\begingroup$ Can you give me an example of $n$ such that $n^{2} \equiv 2 \pmod 3$? ;) (To prove there is no such $n$, use the fact that congruence classes are multiplicative: for each $n$, $n$ is congruent to $0, 1, $ or $2 \pmod 3$. Then compute $n^{2}$ in each case. $0$ and $1$ are obvious. But $2^{2} = 4 \equiv 1 \pmod 3$) $\endgroup$ – Alex Wertheim Dec 28 '13 at 4:30
6
$\begingroup$

If $3$ divides $n^2+1$ then it must have solution modulo $3$. But clearly

$0^2+1\equiv 1 \pmod 3$

$1^2+1 \equiv 2 \pmod 3$

$2^2+1 \equiv 5 \equiv 2 \pmod 3$

Otherwise put $n=3k,3k+1,3k+2$ and see that $3$ never divides it

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

Another way: $ $ notice that $\,3\,$ divides one of $\ \color{#0a0}{n\!-\!1,\,n,\,n\!+\!1}.\ $ Therefore

$\ \ \ \color{#c00}{3\mid n^2\!+1}\Rightarrow\ 3\mid 2 = (\color{#c00}{n^2\!+1})(2\!-\!n^2)+\color{#0a0}{(n\!-\!1)n^2(n\!+\!1)},\ $ contradiction.

Remark $\ $ The above implies coprime $\,n^2\!+1\,$ and $\,n^3\!-n = (n\!-\!1)n(n\!+\!1),\,$ except when $\,n\,$ is odd, when they have gcd $= 2.\,$ The above linear relation between them is simply the Bezout identity for their gcd, considered as a polynomial over $\Bbb Q$ (which can be computed mechanically using the extended Euclidean algorithm). Though this approach is not as efficient as using modular arithmetic, it highlights an interesting viewpoint that often proves useful: often properties of integers (numbers) are special cases of properties of polynomials (functions).

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Every integer $n$ can be written in the form $3m+k$, where $m$ is a non-negative integer and $k = 0, 1, $ or $2$. (This is a particular case of the result that for any positive integer $j$, every integer $n$ can be written in the form $jm+k$, where $m$ is a non-negative integer and $k$ is an integer such that $0 \le k < j$.)

Therefore $n^2+1 =(3m+k)^2+1 =9m^2+6mk+k^2+1 =3(3m^2+2mk)+k^2+1 $.

If $3 \mid n^2+1$, then $3 \mid k^2+1$. But the possible values of $k^2+1$ are $1, 2, $ and $5$ (for $k = 0, 1, 2$, respectively), and $3$ does not divide any of them.

Therefore $3$ does not divide $n^2+1$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Divide $n$ by $3$ and let $Q$ be the quotient and $R$ the remainder. So

$$ n = 3\,Q + R$$ $$n^2+1 = 9\,Q^2 + 6 \, Q\, R + R^2 +1$$ $R$ can only be $0$, or $1$ or $2$. Now argue that in all cases $n^2+1$ is not divisible by $3$.

Not divisibility depends only on $R$ i.e. only on $n \mod 3$. From your question, it looks like you are just starting on number theory. You will soon realize that most problems require you to look only at the remainder.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Since $n-1,n,n+1$ are three successive integers so one of them must be divisible by 3 hence there product must be divisible by $3$ i.e. $3|(n-1)n(n+1) \implies 3|n^3-n$ , now

$3|n^2+1 \implies 3|n(n^2+1) \implies 3|n^3+n \implies 3|n^3+n-(n^3-n) \implies 3|2n$ , since 3 does

not divide $2$ so $3|n \implies 3|n^2 \implies 3|n^2+1-n^2 \implies 3|1$ , contradiction !

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

$n= 0 \pmod3 \implies n^2 + 1 = 1\pmod3$,

$n = 1\pmod3 \implies n^2 + 1 = 2\pmod3$,

$n = 2\pmod3 \implies n^2 + 1 = 2\pmod3$.

So $n^2 + 1$ is not a multiple of $3$ for any $n$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Note that the statement mathematically means: $$ 3 \mid (n^2 + 1) \implies n^2 + 1 \equiv 0 \pmod 3 \equiv n^2 \equiv -1 \equiv 2 \pmod 3. $$ Is this ever possible?

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}% \newcommand{\dd}{{\rm d}}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\half}{{1 \over 2}}% \newcommand{\ic}{{\rm i}}% \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\ol}[1]{\overline{#1}}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ For $n = 1$, it's obvious since $3 \not|\ 2$. Let's assume $3 \not|\ n^{2} + 1$. Then, $n^{2} + 1 = 3p + \delta$ for $p, \delta$ integers and $\delta = 1, 2$: $$ \pars{n + 1}^{2} + 1 = n^{2} + 1 + 2n + 1 = 3p + \delta + 2n + 1 $$ If $\delta = 1$, $\delta + 2n + 1 = 2\pars{n + 1}$ which is even.

If $\delta = 2$, $\delta + 2n + 1 = 2n + 3\quad\imp\pars{n + 1}^{2} + 1 = 3\pars{p + 1} + 2n$: The first term is a multiple of $3$ but the second is even.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.