Prove that there are no positive integers $a$ and $b$ such that for all different primes $p$ and $q$ greater than $1000$, the number $ap+bq$ is also prime.
Problem
Source:
Tags: modular arithmetic, blogs
25.05.2007 03:24
Assume that such integers $a,b$ exist. Let us fix $p=1009.$ Then $1009a+bq$ is prime for every prime $q>1009.$ Choose any prime $r$ not dividing $b.$ Then the congruence $1009a+bx \equiv 0\pmod{r}$ has a solution $x\equiv c\pmod{r}.$ According to Dirichlet's theorem, there are infinitely many primes in the sequence $c+r,\ c+2r,\dots.$ Let $q>1009$ be a prime from this sequence. Then $1009a+bq>r$ and it is divisible by $r$ (thus, not prime). Contradiction proves that there are no such $a,b.$
30.04.2008 16:26
You don't need Dirichlet. There are infinitely many primes greater than 1000. Thus there are 2 distinct primes $ p<q$ that are the same residue modulo $ a+b$. Say $ q=p+(a+b)k$. Then $ ap+bq=ap+bp+bk(a+b)=(a+b)(p+bk)$ is not prime. Luke See my puzzle blog at http://bozzball.blogspot.com/