# If $p \not = 5$ is an odd prime, prove that either $p^2+1$ or $p^2-1$ is divisible by $10$?

I was able to find a solution to this problem, but only by using a couple extra tools that are later in the book$^{1}$. So far the book only covered basic divisibility, $gcd$, and the fundamental theorem of arithmetic; it did not cover modular arithmetic, and altough we did cover the division algorithm, we did not cover divisibility rules (i.e. if a number ends in $5$ or $0$, then it is divisible by $5$). Is there any way of proving this with only the above tools? (I will point out what I used from future chapters in my solution)

My Solution

Suppose $10 \nmid p^2-1 = (p+1)(p-1)$. Then $5 \nmid (p+1)$ and $5 \nmid (p-1)$.

Odd primes can only have last digits of $1, 3, 7, 9$ (I used the divisibility rule that a number ending in $0$ or $5$ is divisible by $5$, which is in the next chapter). Since $5 \nmid (p+1)$ and $5 \nmid (p-1)$, the last digit of $p$ is either $3$ or $7$. If we write $p$ as $10n+3$ or $10n+7$, then square and add $1$, we get a multiple of $10$. (The fact that any integer with a last digit of $k$ can be written as $10n+k$ is also something from a future chapter)

Elemntary Nuber Theory by David Burton 6th ed., Section 3.1 # 10

• It's correct, but it can be repharsed very simply : if the prime isn't five, it doesn't end with five, neither does it's square. But the square has to be odd, and can't end with $3,5,7$, so it has to end with $1$ or $9$, which finishes the argument. – астон вілла олоф мэллбэрг Oct 8 '16 at 0:43
• No need for the letter $p$ to be prime, just $\gcd(p, 10) = 1.$ – Will Jagy Oct 8 '16 at 0:58

If $p\neq 5$ is an odd prime, its square $p^2$ is also odd, thus $p^2-1$ and $p^2+1$ are both even.
Now, since an odd prime $p\neq 5$ must (as you mention in your post) be: $$p\equiv1,3,7 \textrm{ or }9 \mod 10$$ its square will be $$p^2\equiv1,-1,-1\textrm{ or }1 \mod 10$$ which answers your question.