Determine (with proof) the set of all prime numbers

[Math100]

Homework Statement

Determine (with proof) the set of all prime numbers that can divide two successive integers of the form $n^{2}+3$.

Relevant Equations

None.

Proof:

Let $p$ be the prime divisor of two successive integers $n^{2}+3$ and $(n+1)^{2}+3$.
Then $p\mid [(n+1)^{2}+3-(n^{2}+3)]\implies p\mid (2n+1)$.
Observe that $p\mid (n^{2}+3)$ and $p\mid (2n+1)$.
Now we see that $p\mid [(n^{2}+3)-3(2n+1)]\implies p\mid (n^{2}-6n)\implies p\mid [n(n-6)]$.
Since $p\nmid n$, it follows that $p\mid (n-6)$.
By Euclidean Algorithm, we have that $p\mid (2n+1)\implies p\mid [2(n-6)+13]$.
Therefore, the set of all prime numbers that can divide two successive integers of the form $n^{2}+3$ is ${13}$.

 

[fresh_42]

Homework Statement:: Determine (with proof) the set of all prime numbers that can divide two successive integers of the form $n^{2}+3$.
Relevant Equations:: None.

Proof:

Let $p$ be the prime divisor of two successive integers $n^{2}+3$ and $(n+1)^{2}+3$.
Then $p\mid [(n+1)^{2}+3-(n^{2}+3)]\implies p\mid (2n+1)$.
Observe that $p\mid (n^{2}+3)$ and $p\mid (2n+1)$.
Now we see that $p\mid [(n^{2}+3)-3(2n+1)]\implies p\mid (n^{2}-6n)\implies p\mid [n(n-6)]$.
Since $p\nmid n$, it follows that $p\mid (n-6)$.

Why is $p\mid n$ impossible? If $p|n$ then $p|((n^2+3) -n\cdot n)$ and thus $p=3.$ However, if $3|n$ then $3\nmid (n^2+2n+4)=((n+1)^2+3).$

Now, I see that $p\nmid n.$

By Euclidean Algorithm, we have that $p\mid (2n+1)\implies p\mid [2(n-6)+13]$.

Wait again. We know $p|(2n+1)$ and $p|(n-6)$. So $p|((2n+1)-2\cdot (n-6))=13,$ i.e. $p=13.$

Therefore, the set of all prime numbers that can divide two successive integers of the form $n^{2}+3$ is ${13}$.

Yes, that is right.

It wasn't asked for, but is there an example of such an $n$?

 

[Math100]

Why is $p\mid n$ impossible? If $p|n$ then $p|((n^2+3) -n\cdot n)$ and thus $p=3.$ However, if $3|n$ then $3\nmid (n^2+2n+4)=((n+1)^2+3).$

Now, I see that $p\nmid n.$

Wait again. We know $p|(2n+1)$ and $p|(n-6)$. So $p|((2n+1)-2\cdot (n-6))=13,$ i.e. $p=13.$

Yes, that is right.

It wasn't asked for, but is there an example of such an $n$?

Should I include/add why $p\nmid n$ in this proof just like how you did it above? And an example of such an $n$ is $6$.

 

[fresh_42]

Should I include/add why $p\nmid n$ in this proof just like how you did it above? And an example of such an $n$ is $6$.

I'd say yes because it is (at least to me) not obvious. You could as well start with the exclusion of $p=3$ in which case $p\nmid n$ becomes obvious from $p|(n^2+3).$

Here are some more ...

1​	4​	0,3076923077​
2​	7​	0,5384615385​
3​	12​	0,9230769231​
4​	19​	1,4615384615​
5​	28​	2,1538461538​
6​	39​	3​
7​	52​	4​
8​	67​	5,1538461538​
9​	84​	6,4615384615​
10​	103​	7,9230769231​
11​	124​	9,5384615385​
12​	147​	11,3076923077​
13​	172​	13,2307692308​
14​	199​	15,3076923077​
15​	228​	17,5384615385​
16​	259​	19,9230769231​
17​	292​	22,4615384615​
18​	327​	25,1538461538​
19​	364​	28​
20​	403​	31​
21​	444​	34,1538461538​
22​	487​	37,4615384615​
23​	532​	40,9230769231​
24​	579​	44,5384615385​
25​	628​	48,3076923077​
26​	679​	52,2307692308​
27​	732​	56,3076923077​
28​	787​	60,5384615385​
29​	844​	64,9230769231​
30​	903​	69,4615384615​
31​	964​	74,1538461538​
32​	1027​	79​
33​	1092​	84​
34​	1159​	89,1538461538​
35​	1228​	94,4615384615​
36​	1299​	99,9230769231​
37​	1372​	105,5384615385​
38​	1447​	111,3076923077​
39​	1524​	117,2307692308​
40​	1603​	123,3076923077​
41​	1684​	129,5384615385​
42​	1767​	135,9230769231​
43​	1852​	142,4615384615​
44​	1939​	149,1538461538​
45​	2028​	156​
46​	2119​	163​
47​	2212​	170,1538461538​
48​	2307​	177,4615384615​
49​	2404​	184,9230769231​
50​	2503​	192,5384615385​