$\gcd(p, qx_1 + rx_2) = 1$ for primes $p,q,r \ge 2^k$ and $x_1, x_2 < 2^k$

Question

Suppose I have three primes $p,q,r$ that are $\ge 2^k$ each. Suppose I also have two values $x_1, x_2$ that are $< 2^k$ each.

I am wondering if it is the case that, for all such $p,q,r$ and $x_1,x_2$, we have $\gcd(p, qx_1 + rx_2) = 1$.

I was trying to come up with a counter-example and show that $\exists x_1, x_2$, both $< 2^k$, such that $qx_1 + rx_2 = p t$, for some $t$. Since $q$ and $r$ are primes, I know that $\exists$ Bezout coefficients $(a,b)$, with $|a|=|b|\le |q|=|r|$ such that:

\begin{align} aq + br &= 1 \end{align}

Then, I could note that: \begin{align} q(apt) + r(bpt) &= pt \end{align} ...and set $x_1 = apt$ and $x_2 = bpt$, but they will not be less than $2^k$.

Is there a way to come up with a counter-example (or show this holds)?

Answer 1

Simply taking $q$ to be a prime that is $-1\mod p$ and $r$ to be a prime that is $1\mod p$, we see that $x_1 = x_2 = 1$ work.

By Dirichlet's Theorem on primes in arithmetic progressions, for every prime $p$ there are infinitely many $q, r$ that work, but a concrete example is $p = 3, q = 5, r = 7$ (and $k = 1$).

EDIT: In fact, if we take any three primes $p,q,r$ such that $2^{k+1}>q>p>r>2^k$ then by simply taking $x_1=p-r, x_2=q-p$ we have

$x_1 \cdot q + x_2 \cdot r = p \cdot (q+r) \equiv 0 \mod p$

And clearly $x_1, x_2 < 2^k$

Answer 2

To get examples where $p,q,r$ are large and as close together as possible, while $x_1, x_2$ are as small as possible, let $p$ be any balanced prime and let $q,r$ be the primes before and after it. Take $x_1 = x_2 = 1$. It's conjectured that there are infinitely many balanced primes, giving infinitely many such examples.

For example, $1103$ is a balanced prime, because it is the average of $1097$ and $1109$, which are the primes before and after it. So we get the example $\gcd(1103, 1097 + 1109) = 1103 > 1$.