1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – астон вілла олоф мэллбэрг Oct 8 '16 at 0:43
  • $\begingroup$ No need for the letter $p$ to be prime, just $\gcd(p, 10) = 1.$ $\endgroup$ – Will Jagy Oct 8 '16 at 0:58
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.