If $\gcd(n,q_1)=1$ then show that $\gcd(n+tq_1,q)=1$ for some $t$

Question

If $q=q_1\cdot q_2$ and $(q,n)=a$ and $(n,q_1)=1$ then how to select $t$ s.t. $(n+tq_1,q)=1$

bezout implies that $\exists r,s$ s.t. $rn+sq_1=1$ and this means $(rn+sq_1,q)=1$ but how to get rid of $r$ ?

Answer 1

While I do not have a direct formula for $t$, we can prove that it exists. However, it is a "bulldozer" argument that uses Dirichlet's Theorem.

It states that the sequence $\{ n + t q_1 \}_{t \in \mathbb{N}}$ contains infinitely many primes. Hence, all we have to do is choose a $t$ such that $n + t q_1$ is a prime larger than $q$, and we are done.

Answer 2

An explicit construction: take $t$ to be the product of those primes that divide $q$ but not $n$.

We show that this works. Consider a prime $p$ dividing $q$.

• If $p$ divides $n$ then $p$ does not divide $t$ (by our choice of $t$) or $q_1$ (by $\gcd(n,q_1)=1$). Hence $p$ does not divide $n+tq_1$.
• If $p$ does not divide $n$ then $p$ divides $t$, so $p$ does not divide $n+tq_1$.

In conclusion, no prime $p$ dividing $q$ can divide $n+tq_1$, so $\gcd(q,n+tq_1)=1$ for this choice of $t$.