4
$\begingroup$

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

  • 1
    Yes: look up Dirichlet's theorem on primes in arithmetic progression.2012-12-31
  • 0
    I guess that there is other post here with the same questions but I'm not able to find it.2012-12-31
  • 0
    To expand Geoff's comment: There are infinitely many primes satisfying these congruences.2012-12-31

2 Answers 2

8

$$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.)

  • 0
    Nice aside, Marvis - interesting piece of math trivia.2012-12-31
  • 0
    How many prime numbers like this are out there? any idea or we just need to multiple it by 2 (421)2012-12-31
  • 3
    @Shan By [Dirichlet's theorem on primes](http://en.wikipedia.org/wiki/Dirichlet's_theorem_on_arithmetic_progressions), 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.2012-12-31
  • 0
    I do know about Oval :)2012-12-31
5

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.

  • 0
    Thanks Keith - appreciate it.2012-12-31
  • 0
    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$.2013-01-02