Show that 13 is the largest prime that can divide....

[Math100]

Homework Statement

Show that $13$ is the largest prime 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$.
Since $p\mid n^2+3$ and $p\mid 2n+1$,
it follows that $p\mid a(n^2+3)+b(2n+1)$ for some $a,b\in\mathbb{Z}$.
Suppose $a=4$ and $b=-2n$.
Then $p\mid 4(n^2+3)-2n(2n+1)\implies p\mid 12-2n$.
Note that $p\mid (12-2n)+(2n+1)\implies p\mid 13$.
Thus $p\leq 13$.
Therefore, $13$ is the largest prime that can divide two successive integers of the form $n^2+3$.

 

[Mark44]

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$.
Since $p\mid n^2+3$ and $p\mid 2n+1$,
it follows that $p\mid a(n^2+3)+b(2n+1)$ for some $a,b\in\mathbb{Z}$.

Suppose $a=4$ and $b=-2n$.

Just because $p\mid a(n^2+3)+b(2n+1)$ for some $a,b\in\mathbb{Z}$ doesn't mean that this statement is true for specifically chosen pairs of values of a and b. This is the same kind of mistake you made in your previous thread.

Then $p\mid 4(n^2+3)-2n(2n+1)\implies p\mid 12-2n$.
Note that $p\mid (12-2n)+(2n+1)\implies p\mid 13$.
Thus $p\leq 13$.
Therefore, $13$ is the largest prime that can divide two successive integers of the form $n^2+3$.

 

[fresh_42]

Homework Statement:: Show that $13$ is the largest prime 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$.
Since $p\mid n^2+3$ and $p\mid 2n+1$,
it follows that $p\mid a(n^2+3)+b(2n+1)$ for some $a,b\in\mathbb{Z}$.

... it follows that $p\mid a(n^2+3)+b(2n+1)$ for all $a,b\in\mathbb{Z}$ ...

Suppose $a=4$ and $b=-2n$.
Then $p\mid 4(n^2+3)-2n(2n+1)\implies p\mid 12-2n$.
Note that $p\mid (12-2n)+(2n+1)\implies p\mid 13$.
Thus $p\leq 13$.
Therefore, $13$ is the largest prime that can divide two successive integers of the form $n^2+3$.

Nice proof, except for the minor wording error. With $b=-2n+1$ you can save a step.

 

[PeroK]

Why no larger than 13? Why not only 13?

 

[PeroK]

Here's a better problem. Suppose $p$ divides $n^2 + a$ and $(n+1)^2 + a$, show that $p$ divides $4a + 1$. And that $n = kp + 2a$, for $k = \dots -1, 0, 1, 2, \dots$.

E.g. with $a = 3$, $p = 13$ and $n = 6, 19, 32 \dots$.

 

[Prof B]

Let $p$ be a prime divisor of two successive integers $n^2+3$ and $(n+1)^2+3$.

The word "the" assumes that there is only one. You won't know there is only one until you prove that it is 13.

 

[Prof B]

Why no larger than 13? Why not only 13?

The assumption that p was prime wasn't needed. The only positive integers that can be common divisors of $n^2+3$ and $(n+1)^2 + 3$ are 13 and 1.

 

[Prof B]

Here's a better problem. Suppose $p$ divides $n^2 + a$ and $(n+1)^2 + a$, show that $p$ divides $4a + 1$. And that $n = kp + 2a$, for $k = \dots -1, 0, 1, 2, \dots$.

E.g. with $a = 3$, $p = 13$ and $n = 6, 19, 32 \dots$.

Nice! You can actually take any two polynomials f(n) and g(n) and apply Euclid's algorithm to find their GCD. Then there are two cases

1. If the GCD has degree 1 or higher then f(n) and g(n) will have arbitrarily large common factors
2. If the GCD is a constant c then every common divisor of f(n) and g(n) must be a divisor of c

Such pairs of polynomials could be good for "prove or disprove" questions.