# There are primes $p,q$ such that $\gcd(a,b)=|ap-bq|$

Conjecture:

Given $a,b\in\mathbb Z^+$ there are primes $p,q$ such that $\gcd(a,b)=|ap-bq|$.

I would like help with a proof or a counter-example. Tested for millions of pseudo random numbers.

• @CharlesMadeline: $0\notin\mathbb Z^+$ – Lehs Aug 26 '18 at 21:18
• We know that there are positive integers $u,v$ with $\gcd(a,b)=|ua-vb|$, so the question is whether there exists $k$ such that both $u+kb$ and $v+ka$ are prime. Each of these arithmetic sequences contains infinitely many primes. Heuristically (i.e., with a probability-of-being-prime argument), the conjecture ought to be true – Hagen von Eitzen Aug 26 '18 at 21:24

## 1 Answer

Let $a, b>2$ with $b$ very larger than $a$. Suppose the twin prime conjecture true and $b-a=2$

be prime numbers, $gcd(a, b) =1=pa-qb$. If $p, q$ are prime, $ap$ and $qb$ are odd, and $ap-qb$ is even. Contradiction. You cannot have $p=2$ or $q=2$ if $a, b$ are enough big. Suppose, $a, a+2$ are prime, and $q=2$. $p$ is odd so at least $3$. $3a-2(a+2)=a-4$ if $a$ is not big it is not possible.

• $p$ or $q$ could be $2$. – Lehs Aug 26 '18 at 21:30
• @Lehs It's still a good starting point, because that means that either $2a\pm 1$ is a (prime) multiple of $b$, or $2b\pm 1$ is a (prime) multiple of $a$, and it ought to be possible to find an example where that isn't the case. Say $a=11,b=13$. – Arthur Aug 26 '18 at 21:42
• a = 5, b = 29. It is impossible that $1 = |10 - 29q|$ or $1 = |5q - 58|$. – Sasha Kozachinskiy Aug 26 '18 at 21:44
• @SashaKozachinskiy: Are you sure? I've tested it for millions of prime pairs. – Lehs Aug 26 '18 at 21:53
• I guess my test program is erroneous. Have to look at it tomorrow. – Lehs Aug 26 '18 at 22:32