# The greatest common divisor of a product of two primes

Assume $p,q \in \mathbb{P}$, if $a \in \mathbb{Z}$ and $a \notin \{1,p,q,p\cdot q\}$, then I know that $\gcd(a,p\cdot q)=1$. What I can't seem to do is prove it. Number theory (in my opinion) means having loads of facts at your disposal, most of which I just can't remember (it was a long time since I did this).

Can someone please provide me a proof. My thinking was to try a proof by contradiction, but I couldn't find a contraction.

Update: I forgot to add an extra condition to $a$, it must be less than $p\cdot q$ So $a \in \mathbb{Z}$ and $a \notin \{1,p,q,p\cdot q\}$ and $0 \leq a \leq p\cdot q$

• It is not true. Consider $a= 2pq$. Then $\gcd(a,pq) = 2$ – user17762 Jan 9 '13 at 21:43
• If you ever have difficulty proving something, you should spend a little trying to come up with a counterexample. If you succeed then you will have saved yourself a lot of effort! – rschwieb Jan 9 '13 at 21:44
• Even with the extra condition, your hypothesis still isn't true: what is GCD(6, 15)? – Steven Stadnicki Jan 9 '13 at 23:13
• Thanks @StevenStadnicki - you have proved it to me. Can't believe I didn't see this example myself. – Barry Steyn Jan 9 '13 at 23:15

It can't be proven. With $p=2$, $q=3$ and $a=9$, $gcd(9,6)\neq 1$.
You must be remembering something else. It is possible to prove that ($gcd(p,a)=gcd(q,a)=1$) iff $gcd(a,pq)=1$.
• Sorry, but what if $a < p\cdot q$. Is $gcd(a,p\cdot q)=1$ when $a < p\cdot q$. – Barry Steyn Jan 9 '13 at 22:57
• If $p=2,q=5,a=4$ then $a<p\cdot q$ yet $\gcd(a,pq)=2>1$. – coffeemath Jan 10 '13 at 3:07