# If $p$ is prime and $p > 5$, show that when $p$ is divided by 10, the remainder is 1, 3, 7, or 9

If $p$ is prime and $p > 5$, show that when $p$ is divided by 10, the remainder is 1, 3, 7, or 9.

This is a problem from Hungerford's Abstract Algebra: An Introduction. I would like some help on it, it was an example in class. Thanks.

-
Consider the case when the remainder is 2. Then $p = 10 q + 2$ for some integer $q$, so that $p = 2 (5 q + 1)$ is even, but cannot be 2 by the assumption $p > 5$. The other cases are entirely similar, it is useful for you to work them out yourself. – Andreas Caranti Feb 1 '13 at 7:27
$p > 5$ prime means $p$ not divisible by $2$ or $5$. – Benjamin Dickman Feb 1 '13 at 8:26

By the division algorithm, we can write each $p$ as $$p = 10q + r$$ for some quotient $q$ and remainder $0\le r < 10$. As $p$ is prime, clearly $r\neq 0$. $r$ also cannot be even, otherwise $p$ is even. Finally, note that $r \neq 5$ or $5 \mid p$.

For a more brief and algebraic solution, note that $(p,\ 10) = 1$ implies that $p$ is a unit in $\mathbb{Z}/10\mathbb{Z}$. The units of the ring are precisely $1,\ 3,\ 7$ and $9$.

For completeness, you should probably show that there exists primes for each of the remaining congruence classes.

-

You already have a couple of nice ‘mathematical-looking’ answers. In attacking a question like this, though, you might want to start with simple, familiar facts.

The remainder when $p$ is divided by $10$ is simply the last digit of $p$. If the last digit of a number $n$ is $0,2,4,6$, or $8$, what kind of number is $n$? Can it be prime if it’s greater than $2$? If the last digit is $0$ or $5$, what can you say about $n$? Can it be prime and greater than $5$?

These are enough to tell you, at least informally, why the prime $p>5$ must end in $1,3,7$, or $9$, and now you can worry about explaining the reasoning in the previous paragraph a bit more formally.

-
Thank you for the tip, I was not sure how to best ask questions here but I'm learning and will remember that. – grayQuant Feb 1 '13 at 14:36

To say that a prime $p > 5$ gives a remainder of $1, 3, 7$ or $9$ when divided by $10$ is merely remarking that the prime is odd (and not $5$, since all integers ending in five are multiples thereof).

After all, the remainder when divided by $10$ is simply the unit of the number itself, and if that unit was any of $0, 2, 4, 6, 8$ we'd plainly see that it was an even number, and therefore not prime. Likewise with the five.

That said, we could come to the conclusion of your statement by, say, basing an argument on how all primes above $3$ are of the form $6n \pm 1$ (mind you, this follows from an argument akin to the above): the multiples of $6$ begin as follows: $$6, 12, 18, 24, 30\ldots$$ From which we father that the units of such multiples are either $0, 2, 4, 6$ or $8$. Now take the '$\pm 1$' bit into consideration and we find that we have the following units possible: $$1, 3, 5, 7, 9$$ (Remember, a remainder of $-1$ when divided by $10$ is equivalent to a remainder of $9$.)

So, much like the above, we disregard the $5$ since that certainly isn't prime, and we have $1, 3, 7, 9$ leftover, as desired.

-

you are looking for the unit digit of the prime.For prime $p\neq 2$, unit digit is odd which means $p\pmod {10}\in\{1,3,5,7,9\}$

Now, for any prime $p\gt 5$, unit git can't be $5$ otherwise it would be divisible by $5$ and hence won't be a prime.

Thus only possible candidates for unit digit of a prime $p\gt 5$ are $\{1,3,7,9\}$

-

This is clear from the Euclidean algorithm. Write the remainder $\rm\: r = (p\ mod\ 10).\:$ By Euclid

$$\rm p\equiv r\,\ (mod\ 10)\ \Rightarrow\ gcd(p,10) = gcd(r,10)$$

In particular,  when the  gcd $= 1,\,$ then: $\rm\,\ p\,$ is coprime to $10$ $\iff$ $\rm\,r\,$ is coprime to $10$

Now, by hypothesis, $\rm\, p\,$ is prime $> 5,\,$ so $\rm\, p\,$ is coprime to $10,\$ thus $\rm\ r\,$ is coprime to $10,\:$ so we infer that $\rm\,r\,$ is odd and coprime to $\,5,\:$ hence $\rm\:r\in \{1,3,7,9\},\,$ since the remainder $\rm\,r\in [0,9].$

Remark $\$ Ditto if we generalize $\rm\,10\,$ to any modulus $\rm\,m\!:\$ if prime $\rm\,p\nmid m\:$ then its remainder $\rm\, p\ mod\ m\,$ is one of the $\,\varphi(m)\,$ remainders coprime to $\rm\,m.\:$ Or, expressed in radix language:

$\quad$ in radix $\rm\,m\!:\$ if $\rm\,n\,$ has units digits $\rm\,r,\$ then $\rm\ n\,$ is coprime to $\rm\, m\iff r\,$ is coprime to $\rm\,m$

-