# Odd prime division problem

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

My proof so far:

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

Let p=2n+1 for some integer n. Then $\displaystyle 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 $\displaystyle p \neq 5$ is an odd prime, prove that either $\displaystyle p^2-1$ or $\displaystyle p^2+1$ is divisible by 10.

My proof so far:

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

Let p=2n+1 for some integer n. Then $\displaystyle 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 $\displaystyle p \equiv 1,\ 3,\ 5,\ 7,\ \mbox{ or }\ 9 \mod 10$; so $\displaystyle p^2 \equiv 1,\ 5,\ \mbox{ or }\ 9 \mod 10$.

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

Hence:

$\displaystyle 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 $\displaystyle p \neq 5$ is an odd prime, prove that either $\displaystyle p^2-1$ or $\displaystyle p^2+1$ is divisible by 10.

My proof so far:

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

Let p=2n+1 for some integer n. Then $\displaystyle 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: $\displaystyle 10k,10k+1,...,10k+9$.
Now examine each of these forms.

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

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

I just realized I forgot $\displaystyle 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.