Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
4  
Since you are new, I want to give some advice about the site: To get the best possible answers, you should explain what your thoughts on the problem are so far. That way, people won't tell you things you already know, and they can write answers at an appropriate level; also, people are much more willing to help you if you show that you've tried the problem yourself. If this is homework, please add the [homework] tag; people will still help, so don't worry. Also, many would consider your post rude because it simply states the problem, and is not a request for help, so consider rewriting it. –  Zev Chonoles Feb 1 '13 at 7:34
3  
$p > 5$ prime means $p$ not divisible by $2$ or $5$. –  Benjamin Dickman Feb 1 '13 at 8:26

6 Answers 6

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
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.

share|improve this answer

Any natural number $n$ can be expressed as $$n=a_k\cdot 10^k + a_{k-1}\cdot 10^{k-1} + \cdots + a_1\cdot 10 + a_0$$

for some natural numbers (including $0$) $k,a_k,\dots , a_1, a_0$. This representation is unique (up to commutation of the products and sums).

Suppose $p\in \mathbb{P}$. Then $p=a_k\cdot 10^k + a_{k-1}\cdot 10^{k-1} + \cdots + a_1\cdot 10 + a_0$.

Clearly the remainder of $a_k\cdot 10^k + a_{k-1}\cdot 10^{k-1} + \cdots + a_1\cdot 10 + a_0$ when divided by $10$ is $a_0$.

Can you conclude?

share|improve this answer
    
This helped me think about the problem. I think using the division algorithm is what the author of the book had in mind, just because it was in the previous section. –  grayQuant Feb 1 '13 at 22:03

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\}$

share|improve this answer

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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