Proving an integer problem about the sum of a square number and a prime number

[chwala]

Homework Statement

see attached...

Relevant Equations

number concept

i do not seem to understand part $ii$ of this problem...mathematical induction proofs is one area in maths that has always boggled me

let $n=3, p=7, ⇒m=4$
therefore,
$7=(4-3)(4+3)$
$7=1⋅7$
$1, 7$ are integers...$p$ is prime.

i am attempting part $iii$ in a moment...

 

[FactChecker]

Identify exactly which step of his "proof" is the first wrong statement and explain why it is wrong.

 

[fresh_42]

Homework Statement:: see attached...
Relevant Equations:: number concept

i do not seem to understand part $ii$ of this problem...mathematical induction proofs is one area in maths that has always boggled me View attachment 286161
let $n=3, p=7, ⇒m=4$
therefore,
$7=(4-3)(4+3)$
$7=1⋅7$
$1, 7$ are integers...$p$ is prime.

i am attempting part $iii$ in a moment...

This is not a counterexample: $1^2+7=8 \neq m^2$. You need to find an example for $n^2+p=m^2$.

With such an example in mind, you can check Charlie's proof step by step and see what was wrong.

 

[chwala]

This is not a counterexample: $1^2+7=8 \neq m^2$. You need to find an example for $n^2+p=m^2$.

With such an example in mind, you can check Charlie's proof step by step and see what was wrong.

am getting lost here, i picked $n=3, p=7$ to realize $3^2+7=4^2$ or i am missing something?

 

[fresh_42]

am getting lost here, i picked $n=3, p=7$ to realize $3^2+7=4^2$ or i am missing something?

Sorry, you are right. I thought you had $1$ and $7$. My fault. I had a smaller counterexample in mind. You can use the true definition of prime.
$$
p\,|\,a\cdot b \Longrightarrow p\,|\,a \text{ or } p\,|\,b \text{ or } p=\pm 1
$$

 

[hutchphd]

I think the problem with Charlie's "proof" is a little more subtle. Carefully consider what he is actually proving...

 

[chwala]

aaaargh...i was missing this for part $iii$, one has to use the relationship...
$(n+1)^2-n^2=2n+1$
given $2n+1=853$
if follows that, $n=426$,
therefore the two square numbers are $426$ and $427$

 

[chwala]

to answer part $ii$, i realize that as long as $m-n=1$, then we shall always have a prime number $p$ which contradicts Charlie's statement.

 

[Mark44]

to answer part ii, i realize that as long as m−n=1, then we shall always have a prime number which contradicts Charlie's statement.

Right...

 

[chwala]

Sorry, you are right. I thought you had $1$ and $7$. My fault. I had a smaller counterexample in mind. You can use the true definition of prime.
$$
p\,|\,a\cdot b \Longrightarrow p\,|\,a \text{ or } p\,|\,b \text{ or } p=\pm 1
$$

i see that modular arithmetic...is also applicable.

 

[fresh_42]

i see that modular arithmetic...is also applicable.

It is the actual definition of primality: if it divides a product then it has to divide a factor. The other definition is strictly irreducibility: cannot be factored. They are the same in rings like the integers, but this is a theorem. The true definition is often more convenient. In the case above, it is probably easier to take the irreducibility. The correct conclusion would be $m-n=\pm 1$ and $p=m+n$ or $p=m-n$ and $m+n=\pm 1$. So $p$ is still a prime and the contradiction is none.

 

[hutchphd]

to answer part $ii$, i realize that as long as $m-n=1$, then we shall always have a prime number $p$ which contradicts Charlie's statement.

We know that his proof cannot be correct. You are asked to show explicitly and exactly what he does that leads him astray. ( you would get zero for this answer were I grading it! You are correct but it does not answer the question.) I find it an interesting question.

 

[chwala]

We know that his proof cannot be correct. You are asked to show explicitly and exactly what he does that leads him astray. ( you would get zero for this answer were I grading it! You are correct but it does not answer the question.) I find it an interesting question.

I may appreciate your input on this...

 

[chwala]

We know that his proof cannot be correct. You are asked to show explicitly and exactly what he does that leads him astray. ( you would get zero for this answer were I grading it! You are correct but it does not answer the question.) I find it an interesting question.

...by him expressing the difference of two squares as two factors is where the problem is as one of the factors of $p$ could be $1$.

 

[hutchphd]

You are correct. I was thinking incorrectly. Apologies.

 

[jbriggs444]

Homework Statement:: see attached...
Relevant Equations:: number concept

mathematical induction proofs is one area in maths that has always boggled me

The proof attempt by Charlie does not involve mathematical induction.

That said, if one is attempting to prove a "for all" type statement involving a set of integers, an inductive proof would be a plausible way to proceed.

The statement Charlie has been asked to prove takes the form:

For all [ordered pairs of integers m and n], [some statement about that pair]​

The proof technique that Charlie has employed takes the form:

If I can prove the statement for arbitrary [ordered pair] then it follows that it is true for all [ordered pairs].​

Perform indirect proof that the statement is true for arbitrary pair (m,n)​

​

Draw the conclusion.​

An inductive proof for ordered pairs would be trickier to phrase. One would likely nest one induction inside another. Much more complicated than what Charlie has here. It would involve at least a base case (e.g. prove the statement for m=n=1) and an iterative case (e.g. prove that if the statement holds for (m,n) then it also holds for (m+1,n)).

 

[chwala]

The proof attempt by Charlie does not involve mathematical induction.

That said, if one is attempting to prove a "for all" type statement involving a set of integers, an inductive proof would be a plausible way to proceed.

The statement Charlie has been asked to prove takes the form:

For all [ordered pairs of integers m and n], [some statement about that pair]​

The proof technique that Charlie has employed takes the form:

If I can prove the statement for arbitrary [ordered pair] then it follows that it is true for all [ordered pairs].​

Perform indirect proof that the statement is true for arbitrary pair (m,n)​

​

Draw the conclusion.​

An inductive proof for ordered pairs would be trickier to phrase. One would likely nest one induction inside another. Much more complicated than what Charlie has here. It would involve at least a base case (e.g. prove the statement for m=n=1) and an iterative case (e.g. prove that if the statement holds for (m,n) then it also holds for (m+1,n)).

I know that...my statement was just in general terms..in reference to problems that are similar ...to mathematical induction being a challenge ...cheers

 

[haruspex]

It would involve at least a base case (e.g. prove the statement for m=n=1) and an iterative case (e.g. prove that if the statement holds for (m,n) then it also holds for (m+1,n)).

... and holds for (m,n+1).

 

[PeroK]

Note:

Every odd number is the difference of two consecutive squares.