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

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

$$a(x-x')+py-qy'=1-ax'-qy'$$.

Not sure where to go from here. Hints appreciated.

## marked as duplicate by Bill Dubuque algebra-precalculus StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jan 26 at 18:31

$$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?