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.

Is there a prime number $p > 10$ such that when it is divided by 3 or 5 or 7 gives a remainder of 1, i.e.:

$p \equiv 1 \pmod{3}, p \equiv 1 \pmod{5}, p \equiv 1 \pmod{7}$.

share|improve this question
1  
Yes: look up Dirichlet's theorem on primes in arithmetic progression. –  Geoff Robinson Dec 31 '12 at 17:48
    
I guess that there is other post here with the same questions but I'm not able to find it. –  Sigur Dec 31 '12 at 17:48
    
To expand Geoff's comment: There are infinitely many primes satisfying these congruences. –  Andres Caicedo Dec 31 '12 at 17:54
add comment

2 Answers

up vote 8 down vote accepted

$$x \equiv 1 \pmod{3}$$ $$x \equiv 1 \pmod{5}$$ $$x \equiv 1 \pmod{7}$$ Hence, $$x \equiv 1 \pmod{105}$$ Since we want $x$ to be a prime, we have $$x \equiv 1 \pmod{210}$$ $x=211$ happens to be a prime.

As an aside and completely irrelevant to the post, one of G H Hardy's desire was to make a match-winning score of $211$ not-out in cricket in the last innings at Oval. (since $211$ is the first prime after $200$ and G H Hardy had a great passion for cricket. Oval is one of the most famous cricket ground in England.)

share|improve this answer
    
Nice aside, Marvis - interesting piece of math trivia. –  Conan Wong Dec 31 '12 at 17:59
    
How many prime numbers like this are out there? any idea or we just need to multiple it by 2 (421) –  Shan Dec 31 '12 at 18:02
3  
@Shan By Dirichlet's theorem on primes, there are infinitely many primes. As a crude way of saying, $\dfrac1{80}$ of all the primes are of this form, the number $80$ appearing in the denominator since $80 = \phi(220)$ i.e. there are $80$ numbers less than $220$ and relatively prime to it. –  user17762 Dec 31 '12 at 18:05
    
I do know about Oval :) –  Shan Dec 31 '12 at 18:20
add comment

By the Chinese Remainder Theorem, the system of linear congruences:

$$x \equiv 1 (mod \ 3)$$ $$x \equiv 1 (mod \ 5)$$ $$x \equiv 1 (mod \ 7)$$

yields the solution $x \equiv 1 (mod \ 105)$, since 3, 5 and 7 are pairwise coprime and their product is 105.

Since we are looking for positive integers, we consider $x = 1, 106, 211,...$ and we need not look further since 211 is a prime.

share|improve this answer
    
+1 for mentioning the Chinese Remainder Theorem. –  KeithS Dec 31 '12 at 19:59
    
Thanks Keith - appreciate it. –  Conan Wong Dec 31 '12 at 20:34
    
TeX note: if you use \pmod{3} instead of ` (mod 3)` the upright font will be used instead of the italics which makes it look like the product $mod=m\cdot o\cdot d$ or the composition $m\circ d$. –  Charles Jan 2 '13 at 16:51
add comment

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.