If ## p\neq5 ## is an odd prime, prove that either ## p^{2}-1 ## or....

[Math100]

Homework Statement

If $p\neq5$ is an odd prime, prove that either $p^{2}-1$ or $p^{2}+1$ is divisible by 10.

Relevant Equations

None.

Proof:

Suppose $p\neq5$ is an odd prime.
Applying the Division Algorithm produces:
$p=10q+r$ where $0\leq r\leq 10$,
where there exist unique integers $q$ and $r$.
Note that $p\equiv 1, 3, 7$ or $9$ mod $10$.
This means $p^{2}\equiv 1, -1, -1$ or $1$ mod $10$.
Then we have $p=10q+1, p=10q+3, p=10q+7$ or $p=10q+9$.
Now we consider four cases.
Case #1: Suppose $p=10q+1$ for some $q\in\mathbb{Z}$.
Then we have $p^{2}-1=(10q+1)^{2} -1 =100q^{2} +20q+1-1 =100q^{2}+20q =10(10q^{2}+2q) =10m$,
where $m=10q^{2} +2q$ is an integer.
Thus, $p^{2} -1$ is divisible by $10$.
Case #2: Suppose $p=10q+3$ for some $q\in\mathbb{Z}$.
Then we have $p^{2} +1=(10q+3)^{2} +1 =100q^2 +60q+10 =10(10q^{2} +6q+1) =10n$,
where $n=10q^{2} +6q+1$ is an integer.
Thus, $p^{2} +1$ is divisible by $10$.
Case #3: Suppose $p=10q+7$ for some $q\in\mathbb{Z}$.
Then we have $p^{2} +1=(10q+7)^{2} +1 =100q^{2} +140q+49+1 =100q^{2} +140q+50 =10(10q^{2} +14q+5) =10r$,
where $r=10q^{2} +14q+5$ is an integer.
Thus, $p^{2} +1$ is divisible by $10$.
Case #4: Suppose $p=10q+9$ for some $q\in\mathbb{Z}$.
Then we have $p^{2} -1=(10q+9)^{2} -1 =100q^{2} +180q+81-1 =100q^{2} +180q+80 =10(10q^{2} +18q+8) =10s$,
where $s=10q^{2} +18q+8$ is an integer.
Thus, $p^{2} -1$ is divisible by $10$.
Therefore, if $p\neq 5$ is an odd prime, then either $p^{2} -1$ or $p^{2} +1$ is divisible by $10$.

 

[andrewkirk]

We can construct a shorter and simpler proof without so many cases.
NB The latex in the following doesn't quite render properly. The symbol $\not|$ should be a diagonal stroke through (not next to) a vertical stroke, meaning "does not divide".

$$odd(p)\to 2\not|p\to 2\not|p^2\to 2|(p^2-1) \wedge 2|(p^2 +1)$$
$$prime(p)\wedge p\neq 5\to 5\not|p$$
$$5\not|(p^2-1) \to 5\not|((p-1)(p+1))\to 5\not|(p-1)\wedge 5\not|(p+1)$$
So if $prime(p)\wedge 5\not|(p^2-1)$ we know that $5$ doesn't divide $p-1,p$ or $p+1$. What can we then say about whether it divides $p^2-4$ and what does that imply about whether it divides $p^2+1$?

 

[vela]

Once you get to $p^2 \equiv \pm 1~\rm (mod~10)$, can't you conclude $p^2 \mp 1 \equiv 0~\rm (mod~10)$?

 

[PeroK]

Homework Statement:: If $p\neq5$ is an odd prime, prove that either $p^{2}-1$ or $p^{2}+1$ is divisible by 10.
Relevant Equations:: None.

Proof:

Suppose $p\neq5$ is an odd prime.
Applying the Division Algorithm produces:
$p=10q+r$ where $0\leq r\leq 10$,
where there exist unique integers $q$ and $r$.
Note that $p\equiv 1, 3, 7$ or $9$ mod $10$.
This means $p^{2}\equiv 1, -1, -1$ or $1$ mod $10$.

This reminds me a beginner's chess game where several apparently brilliant moves lead to checkmake in one more move, But, instead of giving checkmate, the player plays some other random move and the game continues for another thirty moves!

 

[nuuskur]

Your proof is done in 6 lines.

 

[Math100]

We can construct a shorter and simpler proof without so many cases.
NB The latex in the following doesn't quite render properly. The symbol $\not|$ should be a diagonal stroke through (not next to) a vertical stroke, meaning "does not divide".

$$odd(p)\to 2\not|p\to 2\not|p^2\to 2|(p^2-1) \wedge 2|(p^2 +1)$$
$$prime(p)\wedge p\neq 5\to 5\not|p$$
$$5\not|(p^2-1) \to 5\not|((p-1)(p+1))\to 5\not|(p-1)\wedge 5\not|(p+1)$$
So if $prime(p)\wedge 5\not|(p^2-1)$ we know that $5$ doesn't divide $p-1,p$ or $p+1$. What can we then say about whether it divides $p^2-4$ and what does that imply about whether it divides $p^2+1$?

$5$ divides $p^{2}-4$, and also
$5$ divides $p^{2}+1$.

 

[Math100]

Once you get to $p^2 \equiv \pm 1~\rm (mod~10)$, can't you conclude $p^2 \mp 1 \equiv 0~\rm (mod~10)$?

Sorry, but I do not understand $p^2 \mp 1 \equiv 0~\rm (mod~10)$. Can you please explain what this is?

 

[WWGD]

Sorry, but I do not understand $p^2 \mp 1 \equiv 0~\rm (mod~10)$. Can you please explain what this is?

It comes down to $a \equiv b ~\rm (mod m) \rightarrow a-b \equiv 0( modm)$, assuming a,b are coprime to m.

 

[Math100]

Your proof is done in 6 lines.

So the first 6 lines in my original proof is sufficient?

 

[haruspex]

So the first 6 lines in my original proof is sufficient?

Just lines 1, 5, 6, plus one more to finish, I'd say.

 

[PeroK]

Sorry, but I do not understand $p^2 \mp 1 \equiv 0~\rm (mod~10)$. Can you please explain what this is?

That's what you had to prove. That $p^2 -1 = 0 \ (mod \ 10)$ or $p^2 + 1 = 0 \ (mod \ 10)$. Or, using the shorthand $\pm$ for "plus or minus"; or, $\mp$ for "minus or plus", you have to show that: $p^2 \mp 1 = 0 \ (mod \ 10)$.

 

[PeroK]

So the first 6 lines in my original proof is sufficient?

Do you not see that you got within one step of a finished proof, but then went off at random in a different direction?

 

[Math100]

That's what you had to prove. That $p^2 -1 = 0 \ (mod \ 10)$ or $p^2 + 1 = 0 \ (mod \ 10)$. Or, using the shorthand $\pm$ for "plus or minus"; or, $\mp$ for "minus or plus", you have to show that: $p^2 \mp 1 = 0 \ (mod \ 10)$.

Okay, here's my revised proof:

Suppose $p\neq5$ is an odd prime.
Note that $p\equiv1, 3, 7$ or $9$ mod $10$.
This means $p^{2}\equiv1, -1, -1$ or $1$ mod $10$.
Now we consider two cases.
Case #1: Suppose $p\equiv1$ or $9$ mod $10$.
Then we have $p^{2}\equiv1$ or $81$ mod $10$.
Thus $p^{2}-1\equiv 0$ mod $10$.
Case #2: Suppose $p\equiv3$ or $7$ mod $10$.
Then we have $p^{2}\equiv 9$ or $49$ mod $10$.
Thus $p^{2}+1\equiv 0$ mod $10$.
Therefore, if $p\neq5$ is an odd prime,
then either $p^{2}-1$ or $p^{2}+1$ is divisible by $10$.

 

[haruspex]

Okay, here's my revised proof:

Suppose $p\neq5$ is an odd prime.
Note that $p\equiv1, 3, 7$ or $9$ mod $10$.
This means $p^{2}\equiv1, -1, -1$ or $1$ mod $10$.
Now we consider two cases.
Case #1: Suppose $p\equiv1$ or $9$ mod $10$.
Then we have $p^{2}\equiv1$ or $81$ mod $10$.
Thus $p^{2}-1\equiv 0$ mod $10$.
Case #2: Suppose $p\equiv3$ or $7$ mod $10$.
Then we have $p^{2}\equiv 9$ or $49$ mod $10$.
Thus $p^{2}+1\equiv 0$ mod $10$.
Therefore, if $p\neq5$ is an odd prime,
then either $p^{2}-1$ or $p^{2}+1$ is divisible by $10$.

That's fine, but I would have written it less wordily as
$p^{2}\equiv1, -1, -1$ or $1$ mod $10$
$p^{2}+1\equiv2, 0, 0$ or $2$ mod $10$
$p^{2}-1\equiv0, -2, -2$ or $0$ mod $10$
either $p^{2}-1$ or $p^{2}+1 \equiv0$ mod $10$.

 

[sysprog]

NB The latex in the following doesn't quite render properly. The symbol $\not|$ should be a diagonal stroke through (not next to) a vertical stroke, meaning "does not divide".

What you used should have worked, but given that it didn't, you could use \nmid instead: $x\nmid y$.

 

[PeroK]

Note that we didn't really need $p$ to be prime here.

If $n$ is odd and not divisible by $5$, then either $n^2 -1$ or $n^2 +1$ is divisible by $10$. It's always worth noticing this sort of thing.