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

• Math100
In summary, the prime number p is divisible by 10 if and only if p is equal to 10q+r for some integers q and r.f

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 ##.

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##?

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)##?

Math100, nuuskur and 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!

Math100 and 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 ##.

andrewkirk
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?

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.

vela and Math100
Your proof is done in 6 lines.
So the first 6 lines in my original proof is sufficient?

So the first 6 lines in my original proof is sufficient?
Just lines 1, 5, 6, plus one more to finish, I'd say.

Math100
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)##.

Math100
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 ##.

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##.

Math100
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##.

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.

sysprog