# Odd prime division problem

• Jan 30th 2008, 09:34 AM
Odd prime division problem
Prove that if $p \neq 5$ is an odd prime, prove that either $p^2-1$ or $p^2+1$ is divisible by 10.

My proof so far:

If $10 | p^2-1$, then we are done. Assume 10 doesn't divide $p^2-1$.

Let p=2n+1 for some integer n. Then $p^2+1 = (2n+1)^2+1=4n^2+4n+1+1=4n^2+4n+2$ so 2 can divide it.
• Jan 30th 2008, 09:49 AM
CaptainBlack
Quote:

Prove that if $p \neq 5$ is an odd prime, prove that either $p^2-1$ or $p^2+1$ is divisible by 10.

My proof so far:

If $10 | p^2-1$, then we are done. Assume 10 doesn't divide $p^2-1$.

Let p=2n+1 for some integer n. Then $p^2+1 = (2n+1)^2+1=4n^2+4n+1+1=4n^2+4n+2$ so 2 can divide it.

Let for an odd prime $p \equiv 1,\ 3,\ 5,\ 7,\ \mbox{ or }\ 9 \mod 10$; so $p^2 \equiv 1,\ 5,\ \mbox{ or }\ 9 \mod 10$.

But as $p$ is a prime other than $5,\ p \not\equiv 5 \mod 10$ and so $p^2 \not\equiv 5 \mod 10$.

Hence:

$p^2 \equiv 1,\ \mbox{ or }\ 9 \mod 10$

which proves the required result.

RonL
• Jan 30th 2008, 10:19 AM
So far our course have not introduce mod yet, is it possible to do this by other means? thank you.
• Jan 30th 2008, 02:48 PM
ThePerfectHacker
Quote:

Prove that if $p \neq 5$ is an odd prime, prove that either $p^2-1$ or $p^2+1$ is divisible by 10.

My proof so far:

If $10 | p^2-1$, then we are done. Assume 10 doesn't divide $p^2-1$.

Let p=2n+1 for some integer n. Then $p^2+1 = (2n+1)^2+1=4n^2+4n+1+1=4n^2+4n+2$ so 2 can divide it.

A number has one of the forms: $10k,10k+1,...,10k+9$.
Now examine each of these forms.

1) $10k$ this is never prime.
2) $10k+2 = 2(5k+1)$ this is only prime for $k=0$, but the prime is odd so it cannot have this form.
3) $10k+3$ since $3,10$ have no common factors this is a possible prime.
4) $10k+4 = 2(5k+2)$ this is never prime.
5) $10k+5 = 5(2k+1)$ this is only prime at $k=0$ and that prime is $5$ which cannot be because $p\not = 5$.
6) $10k+6 = 2(5k+3)$ this is never prime.
7) $10k+7$ a possible prime.
8) $10k+8 = 2(5k+4)$ this is never prime.
9) $10k+9$ a possible prime.

Which means $p$ has one of three forms: $10k+3,10k+7,10k+9$. If you substitute that into $p^2 \pm 1$ you will see it is divisible by $10$. For example, $(10k+3)^2 = 10(10k+6)+9$ so $p^2 + 1$ is divisible. And so on.

I just realized I forgot $10k+1$ - but you get the idea. And do not be afraid of this argument, it might look long but that is because I explained it in detail.