This question already has an answer here:

If $p,q$ are distinct primes and $a$ is not divisible by $p$ or $q$, then $\gcd(a, pq)=1$.

I want to show this using linear combinations, so that a linear combination of $a$, and $py$ will give $1$. So for some $x,y,x',y'$:

$ax+py = 1 = ax'+qy'$, and


Not sure where to go from here. Hints appreciated.


marked as duplicate by Bill Dubuque algebra-precalculus Jan 26 at 18:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


$ax+py = 1$ and $ ax'+qy'=1$. Rearranging, we have $py = 1-ax$ and $qy'=1-ax'$. Multiplying, we get $$pyqy'=(1-ax)(1-ax')=1-a (x+x')+a^2xx'.$$

Hence $$pq(yy')+a (x+x'-axx')=1. $$


If $a$ is not divisible by $p$ or $q$ then indeed there exist integers $x$, $x'$, $y$, and $y'$ such that $$ax+py=1\qquad\text{ and }\qquad ax'+qy'=1.$$ Now isolate $py$ from the first and $qy'$ from the second equation, and multiply the two results together. Can you finish from here?


Not the answer you're looking for? Browse other questions tagged or ask your own question.