Proving $\gcd(a,p_1p_2)>1$ $\Rightarrow$ $p_1\mid a$ xor $p_2\mid a$ using Euclid's Lemma Consider the lemma:
If $\gcd(a, p_1p_2)>1$, then either $p_1\mid a$ or $p_2\mid a$.
How can this be proved using Euclid's Lemma?
 A: The only divisors of $p_1 p_2$ are $1$, $p_1$, $p_2$, and $p_1 p_2$.
Therefore if $\gcd(a, p_1 p_2)\ne 1$ then either $\gcd(a, p_1 p_2) = p_1$ or $\gcd(a, p_1 p_2)=p_2$ or $\gcd(a, p_1 p_2)= p_1 p_2$.
Hence either $p_1\mid a$ or $p_2 \mid a$ or $p_1 p_2\mid a$, and if we take "or" to be inclusive, this means either $p_1\mid a$ or $p_2\mid a$.
(I don't know why you have "xor" in the subject line.  The proposition is true with an inclusive "or", but not with an exclusive "or".)
A: Hint $ $ By Euclid, if $\,\gcd(a,p_1)=1=\gcd(a,p_2)\,$ then $\,\gcd(a,p_1 p_2)= 1,\,$ contra hypothesis. Hence at least one of the gcds is $> 1,\,$ so $\,p_1\mid a\,$ or $\ p_2\mid a\,$ (note $\,\gcd(a,p_i) = p_i$ or $\,1,\,$ by $\,p_i$ prime).
Or, using the form of Euclid's Lemma that prime $\,p\mid ab\,\Rightarrow\,p\mid a\,$ or $\,p\mid b,\,$ let $\,d = \gcd(a,p_1p_2)\,$ By $\,d>1\,$ it has a prime factor $\,p\,$ and $\,p\mid d\mid p_1 p_2\Rightarrow\,p\mid p_1p_2\,$  hence $\,p\mid p_1\,$ or $\,p\mid p_2\,$ by Euclid. If $\,p\mid p_1\,$ then $\,p = p_1\,$ so $\,p_1\mid d\mid\,a\,\Rightarrow\,p_1\mid a.\,$ Similarly $\,p\mid p_2\,\Rightarrow\,p_2\mid a.$
