Mixing
$3$ never divides $n^2+1$
$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.
elementary-number-theory divisibility
edited Jan 26 at 2:50
user549397
1,5081418
asked Dec 28 '13 at 4:25
Username UnknownUsername Unknown
1,17742259
$endgroup$
add a comment |
$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.
elementary-number-theory divisibility
edited Jan 26 at 2:50
user549397
1,5081418
asked Dec 28 '13 at 4:25
Username UnknownUsername Unknown
1,17742259
$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
add a comment |
$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.
elementary-number-theory divisibility
edited Jan 26 at 2:50
user549397
1,5081418
asked Dec 28 '13 at 4:25
Username UnknownUsername Unknown
1,17742259
$endgroup$
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.
elementary-number-theory divisibility
elementary-number-theory divisibility
edited Jan 26 at 2:50
user549397
1,5081418
asked Dec 28 '13 at 4:25
Username UnknownUsername Unknown
1,17742259
edited Jan 26 at 2:50
user549397
1,5081418
asked Dec 28 '13 at 4:25
Username UnknownUsername Unknown
1,17742259
edited Jan 26 at 2:50
user549397
1,5081418
edited Jan 26 at 2:50
user549397
1,5081418
edited Jan 26 at 2:50
user549397
1,5081418
1,5081418
asked Dec 28 '13 at 4:25
Username UnknownUsername Unknown
1,17742259
asked Dec 28 '13 at 4:25
Username UnknownUsername Unknown
1,17742259
asked Dec 28 '13 at 4:25
Username UnknownUsername Unknown
1,17742259
1,17742259
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
add a comment |
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
12
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
$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
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
$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
add a comment |
10 Answers
10
active
oldest
votes
$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.
$endgroup$
add a comment |
$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}$?
answered Dec 28 '13 at 4:26
Alex WertheimAlex Wertheim
16.1k22848
$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
add a comment |
$begingroup$
If $3$ divides $n^2+1$ then it must have solution modulo $3$. But clearly
$0^2+1equiv 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
edited Dec 28 '13 at 5:54
DanielV
18.1k42755
answered Dec 28 '13 at 4:32
KayokenKayoken
5031314
$endgroup$
add a comment |
$begingroup$
Another way: $ $ notice that $,3,$ divides one of $ color{#0a0}{n!-!1,,n,,n!+!1}. $ Therefore
$ color{#c00}{3mid n^2!+1}Rightarrow 3mid 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).
edited Apr 13 '17 at 12:20
Community♦
1
answered Dec 28 '13 at 5:49
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
add a comment |
$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$.
answered Dec 28 '13 at 4:37
marty cohenmarty cohen
74.5k549129
$endgroup$
add a comment |
$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.
answered Dec 28 '13 at 4:38
user44197user44197
9,0081117
$endgroup$
add a comment |
$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 !
answered Dec 28 '13 at 6:18
Souvik DeySouvik Dey
4,07411459
$endgroup$
add a comment |
$begingroup$
$n= 0 pmod3 implies n^2 + 1 = 1pmod3$,
$n = 1pmod3 implies n^2 + 1 = 2pmod3$,
$n = 2pmod3 implies n^2 + 1 = 2pmod3$.
So $n^2 + 1$ is not a multiple of $3$ for any $n$.
edited Jan 15 '14 at 14:07
Martin Sleziak
44.9k10121274
answered Dec 28 '13 at 4:30
DeepSeaDeepSea
71.3k54488
$endgroup$
add a comment |
$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?
answered Dec 28 '13 at 4:33
Ahaan S. RungtaAhaan S. Rungta
6,53352161
$endgroup$
add a comment |
$begingroup$
$newcommand{+}{^{dagger}}%
newcommand{angles}[1]{leftlangle #1 rightrangle}%
newcommand{braces}[1]{leftlbrace #1 rightrbrace}%
newcommand{bracks}[1]{leftlbrack #1 rightrbrack}%
newcommand{ceil}[1]{,leftlceil #1 rightrceil,}%
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]{,leftlfloor #1 rightrfloor,}%
newcommand{half}{{1 over 2}}%
newcommand{ic}{{rm i}}%
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}%
newcommand{isdiv}{,left.rightvert,}%
newcommand{ket}[1]{leftvert #1rightrangle}%
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]{leftvert, #1 ,rightvert}$
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 = 2pars{n + 1}$ which is even.
If $delta = 2$, $delta + 2n + 1 = 2n + 3quadimppars{n + 1}^{2} + 1 = 3pars{p + 1} + 2n$: The first term is a multiple of $3$ but the second is even.
answered Dec 28 '13 at 6:48
Felix MarinFelix Marin
68.7k7109146
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f620153%2f3-never-divides-n21%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
10 Answers
10
active
oldest
votes
10 Answers
10
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
$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.
$endgroup$
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.
answered Dec 28 '13 at 4:30
user61527
add a comment |
add a comment |
$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}$?
answered Dec 28 '13 at 4:26
Alex WertheimAlex Wertheim
16.1k22848
$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
add a comment |
$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}$?
answered Dec 28 '13 at 4:26
Alex WertheimAlex Wertheim
16.1k22848
$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
add a comment |
$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}$?
answered Dec 28 '13 at 4:26
Alex WertheimAlex Wertheim
16.1k22848
$endgroup$
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}$?
answered Dec 28 '13 at 4:26
Alex WertheimAlex Wertheim
16.1k22848
answered Dec 28 '13 at 4:26
Alex WertheimAlex Wertheim
16.1k22848
answered Dec 28 '13 at 4:26
Alex WertheimAlex Wertheim
16.1k22848
answered Dec 28 '13 at 4:26
Alex WertheimAlex Wertheim
16.1k22848
16.1k22848
$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
add a comment |
$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
$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$
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
$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
add a comment |
$begingroup$
If $3$ divides $n^2+1$ then it must have solution modulo $3$. But clearly
$0^2+1equiv 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
edited Dec 28 '13 at 5:54
DanielV
18.1k42755
answered Dec 28 '13 at 4:32
KayokenKayoken
5031314
$endgroup$
add a comment |
$begingroup$
If $3$ divides $n^2+1$ then it must have solution modulo $3$. But clearly
$0^2+1equiv 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
edited Dec 28 '13 at 5:54
DanielV
18.1k42755
answered Dec 28 '13 at 4:32
KayokenKayoken
5031314
$endgroup$
add a comment |
$begingroup$
If $3$ divides $n^2+1$ then it must have solution modulo $3$. But clearly
$0^2+1equiv 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
edited Dec 28 '13 at 5:54
DanielV
18.1k42755
answered Dec 28 '13 at 4:32
KayokenKayoken
5031314
$endgroup$
If $3$ divides $n^2+1$ then it must have solution modulo $3$. But clearly
$0^2+1equiv 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
edited Dec 28 '13 at 5:54
DanielV
18.1k42755
answered Dec 28 '13 at 4:32
KayokenKayoken
5031314
edited Dec 28 '13 at 5:54
DanielV
18.1k42755
edited Dec 28 '13 at 5:54
DanielV
18.1k42755
edited Dec 28 '13 at 5:54
DanielV
18.1k42755
18.1k42755
answered Dec 28 '13 at 4:32
KayokenKayoken
5031314
answered Dec 28 '13 at 4:32
KayokenKayoken
5031314
answered Dec 28 '13 at 4:32
KayokenKayoken
5031314
5031314
add a comment |
add a comment |
$begingroup$
Another way: $ $ notice that $,3,$ divides one of $ color{#0a0}{n!-!1,,n,,n!+!1}. $ Therefore
$ color{#c00}{3mid n^2!+1}Rightarrow 3mid 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).
edited Apr 13 '17 at 12:20
Community♦
1
answered Dec 28 '13 at 5:49
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
add a comment |
$begingroup$
Another way: $ $ notice that $,3,$ divides one of $ color{#0a0}{n!-!1,,n,,n!+!1}. $ Therefore
$ color{#c00}{3mid n^2!+1}Rightarrow 3mid 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).
edited Apr 13 '17 at 12:20
Community♦
1
answered Dec 28 '13 at 5:49
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
add a comment |
$begingroup$
Another way: $ $ notice that $,3,$ divides one of $ color{#0a0}{n!-!1,,n,,n!+!1}. $ Therefore
$ color{#c00}{3mid n^2!+1}Rightarrow 3mid 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).
edited Apr 13 '17 at 12:20
Community♦
1
answered Dec 28 '13 at 5:49
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
Another way: $ $ notice that $,3,$ divides one of $ color{#0a0}{n!-!1,,n,,n!+!1}. $ Therefore
$ color{#c00}{3mid n^2!+1}Rightarrow 3mid 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).
edited Apr 13 '17 at 12:20
Community♦
1
answered Dec 28 '13 at 5:49
Bill DubuqueBill Dubuque
212k29195654
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Dec 28 '13 at 5:49
Bill DubuqueBill Dubuque
212k29195654
answered Dec 28 '13 at 5:49
Bill DubuqueBill Dubuque
212k29195654
answered Dec 28 '13 at 5:49
Bill DubuqueBill Dubuque
212k29195654
212k29195654
add a comment |
add a comment |
$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$.
answered Dec 28 '13 at 4:37
marty cohenmarty cohen
74.5k549129
$endgroup$
add a comment |
$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$.
answered Dec 28 '13 at 4:37
marty cohenmarty cohen
74.5k549129
$endgroup$
add a comment |
$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$.
answered Dec 28 '13 at 4:37
marty cohenmarty cohen
74.5k549129
$endgroup$
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$.
answered Dec 28 '13 at 4:37
marty cohenmarty cohen
74.5k549129
answered Dec 28 '13 at 4:37
marty cohenmarty cohen
74.5k549129
answered Dec 28 '13 at 4:37
marty cohenmarty cohen
74.5k549129
answered Dec 28 '13 at 4:37
marty cohenmarty cohen
74.5k549129
74.5k549129
add a comment |
add a comment |
$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.
answered Dec 28 '13 at 4:38
user44197user44197
9,0081117
$endgroup$
add a comment |
$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.
answered Dec 28 '13 at 4:38
user44197user44197
9,0081117
$endgroup$
add a comment |
$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.
answered Dec 28 '13 at 4:38
user44197user44197
9,0081117
$endgroup$
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.
answered Dec 28 '13 at 4:38
user44197user44197
9,0081117
answered Dec 28 '13 at 4:38
user44197user44197
9,0081117
answered Dec 28 '13 at 4:38
user44197user44197
9,0081117
answered Dec 28 '13 at 4:38
user44197user44197
9,0081117
9,0081117
add a comment |
add a comment |
$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 !
answered Dec 28 '13 at 6:18
Souvik DeySouvik Dey
4,07411459
$endgroup$
add a comment |
$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 !
answered Dec 28 '13 at 6:18
Souvik DeySouvik Dey
4,07411459
$endgroup$
add a comment |
$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 !
answered Dec 28 '13 at 6:18
Souvik DeySouvik Dey
4,07411459
$endgroup$
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 !
answered Dec 28 '13 at 6:18
Souvik DeySouvik Dey
4,07411459
answered Dec 28 '13 at 6:18
Souvik DeySouvik Dey
4,07411459
answered Dec 28 '13 at 6:18
Souvik DeySouvik Dey
4,07411459
answered Dec 28 '13 at 6:18
Souvik DeySouvik Dey
4,07411459
4,07411459
add a comment |
add a comment |
$begingroup$
$n= 0 pmod3 implies n^2 + 1 = 1pmod3$,
$n = 1pmod3 implies n^2 + 1 = 2pmod3$,
$n = 2pmod3 implies n^2 + 1 = 2pmod3$.
So $n^2 + 1$ is not a multiple of $3$ for any $n$.
edited Jan 15 '14 at 14:07
Martin Sleziak
44.9k10121274
answered Dec 28 '13 at 4:30
DeepSeaDeepSea
71.3k54488
$endgroup$
add a comment |
$begingroup$
$n= 0 pmod3 implies n^2 + 1 = 1pmod3$,
$n = 1pmod3 implies n^2 + 1 = 2pmod3$,
$n = 2pmod3 implies n^2 + 1 = 2pmod3$.
So $n^2 + 1$ is not a multiple of $3$ for any $n$.
edited Jan 15 '14 at 14:07
Martin Sleziak
44.9k10121274
answered Dec 28 '13 at 4:30
DeepSeaDeepSea
71.3k54488
$endgroup$
add a comment |
$begingroup$
$n= 0 pmod3 implies n^2 + 1 = 1pmod3$,
$n = 1pmod3 implies n^2 + 1 = 2pmod3$,
$n = 2pmod3 implies n^2 + 1 = 2pmod3$.
So $n^2 + 1$ is not a multiple of $3$ for any $n$.
edited Jan 15 '14 at 14:07
Martin Sleziak
44.9k10121274
answered Dec 28 '13 at 4:30
DeepSeaDeepSea
71.3k54488
$endgroup$
$n= 0 pmod3 implies n^2 + 1 = 1pmod3$,
$n = 1pmod3 implies n^2 + 1 = 2pmod3$,
$n = 2pmod3 implies n^2 + 1 = 2pmod3$.
So $n^2 + 1$ is not a multiple of $3$ for any $n$.
edited Jan 15 '14 at 14:07
Martin Sleziak
44.9k10121274
answered Dec 28 '13 at 4:30
DeepSeaDeepSea
71.3k54488
edited Jan 15 '14 at 14:07
Martin Sleziak
44.9k10121274
edited Jan 15 '14 at 14:07
Martin Sleziak
44.9k10121274
edited Jan 15 '14 at 14:07
Martin Sleziak
44.9k10121274
44.9k10121274
answered Dec 28 '13 at 4:30
DeepSeaDeepSea
71.3k54488
answered Dec 28 '13 at 4:30
DeepSeaDeepSea
71.3k54488
answered Dec 28 '13 at 4:30
DeepSeaDeepSea
71.3k54488
71.3k54488
add a comment |
add a comment |
$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?
answered Dec 28 '13 at 4:33
Ahaan S. RungtaAhaan S. Rungta
6,53352161
$endgroup$
add a comment |
$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?
answered Dec 28 '13 at 4:33
Ahaan S. RungtaAhaan S. Rungta
6,53352161
$endgroup$
add a comment |
$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?
answered Dec 28 '13 at 4:33
Ahaan S. RungtaAhaan S. Rungta
6,53352161
$endgroup$
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?
answered Dec 28 '13 at 4:33
Ahaan S. RungtaAhaan S. Rungta
6,53352161
answered Dec 28 '13 at 4:33
Ahaan S. RungtaAhaan S. Rungta
6,53352161
answered Dec 28 '13 at 4:33
Ahaan S. RungtaAhaan S. Rungta
6,53352161
answered Dec 28 '13 at 4:33
Ahaan S. RungtaAhaan S. Rungta
6,53352161
6,53352161
add a comment |
add a comment |
$begingroup$
$newcommand{+}{^{dagger}}%
newcommand{angles}[1]{leftlangle #1 rightrangle}%
newcommand{braces}[1]{leftlbrace #1 rightrbrace}%
newcommand{bracks}[1]{leftlbrack #1 rightrbrack}%
newcommand{ceil}[1]{,leftlceil #1 rightrceil,}%
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]{,leftlfloor #1 rightrfloor,}%
newcommand{half}{{1 over 2}}%
newcommand{ic}{{rm i}}%
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}%
newcommand{isdiv}{,left.rightvert,}%
newcommand{ket}[1]{leftvert #1rightrangle}%
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]{leftvert, #1 ,rightvert}$
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 = 2pars{n + 1}$ which is even.
If $delta = 2$, $delta + 2n + 1 = 2n + 3quadimppars{n + 1}^{2} + 1 = 3pars{p + 1} + 2n$: The first term is a multiple of $3$ but the second is even.
answered Dec 28 '13 at 6:48
Felix MarinFelix Marin
68.7k7109146
$endgroup$
add a comment |
$begingroup$
$newcommand{+}{^{dagger}}%
newcommand{angles}[1]{leftlangle #1 rightrangle}%
newcommand{braces}[1]{leftlbrace #1 rightrbrace}%
newcommand{bracks}[1]{leftlbrack #1 rightrbrack}%
newcommand{ceil}[1]{,leftlceil #1 rightrceil,}%
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]{,leftlfloor #1 rightrfloor,}%
newcommand{half}{{1 over 2}}%
newcommand{ic}{{rm i}}%
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}%
newcommand{isdiv}{,left.rightvert,}%
newcommand{ket}[1]{leftvert #1rightrangle}%
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]{leftvert, #1 ,rightvert}$
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 = 2pars{n + 1}$ which is even.
If $delta = 2$, $delta + 2n + 1 = 2n + 3quadimppars{n + 1}^{2} + 1 = 3pars{p + 1} + 2n$: The first term is a multiple of $3$ but the second is even.
answered Dec 28 '13 at 6:48
Felix MarinFelix Marin
68.7k7109146
$endgroup$
add a comment |
$begingroup$
$newcommand{+}{^{dagger}}%
newcommand{angles}[1]{leftlangle #1 rightrangle}%
newcommand{braces}[1]{leftlbrace #1 rightrbrace}%
newcommand{bracks}[1]{leftlbrack #1 rightrbrack}%
newcommand{ceil}[1]{,leftlceil #1 rightrceil,}%
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]{,leftlfloor #1 rightrfloor,}%
newcommand{half}{{1 over 2}}%
newcommand{ic}{{rm i}}%
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}%
newcommand{isdiv}{,left.rightvert,}%
newcommand{ket}[1]{leftvert #1rightrangle}%
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]{leftvert, #1 ,rightvert}$
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 = 2pars{n + 1}$ which is even.
If $delta = 2$, $delta + 2n + 1 = 2n + 3quadimppars{n + 1}^{2} + 1 = 3pars{p + 1} + 2n$: The first term is a multiple of $3$ but the second is even.
answered Dec 28 '13 at 6:48
Felix MarinFelix Marin
68.7k7109146
$endgroup$
$newcommand{+}{^{dagger}}%
newcommand{angles}[1]{leftlangle #1 rightrangle}%
newcommand{braces}[1]{leftlbrace #1 rightrbrace}%
newcommand{bracks}[1]{leftlbrack #1 rightrbrack}%
newcommand{ceil}[1]{,leftlceil #1 rightrceil,}%
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]{,leftlfloor #1 rightrfloor,}%
newcommand{half}{{1 over 2}}%
newcommand{ic}{{rm i}}%
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}%
newcommand{isdiv}{,left.rightvert,}%
newcommand{ket}[1]{leftvert #1rightrangle}%
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]{leftvert, #1 ,rightvert}$
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 = 2pars{n + 1}$ which is even.
If $delta = 2$, $delta + 2n + 1 = 2n + 3quadimppars{n + 1}^{2} + 1 = 3pars{p + 1} + 2n$: The first term is a multiple of $3$ but the second is even.
answered Dec 28 '13 at 6:48
Felix MarinFelix Marin
68.7k7109146
answered Dec 28 '13 at 6:48
Felix MarinFelix Marin
68.7k7109146
answered Dec 28 '13 at 6:48
Felix MarinFelix Marin
68.7k7109146
answered Dec 28 '13 at 6:48
Felix MarinFelix Marin
68.7k7109146
68.7k7109146
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f620153%2f3-never-divides-n21%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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