2

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?

Michael Hardy
  • 1
user38931
  • 57

2 Answers2

2

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".)

Michael Hardy
  • 1
  • Thank you for your reply. The proof you posted is also what I came up with at first as proof. However, I could not and still cannot see where Euclid's Lemma is used? (So I thought, maybe if I try to prove it for XOR instead of OR, then Euclid's Lemma will be used in some way.) – user38931 Apr 28 '14 at 16:40
  • @user38931 The above essentially uses uniqueness of prime factorizations (which is equivalent to Euclid's Lemma). See my answer for one way to explicitly use Euclid's Lemma. There are various forms of EL so you might want to say which one you know. – Bill Dubuque Apr 28 '14 at 16:40
1

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

Bill Dubuque
  • 272,048
  • I learned 'If p|ab, then p|a or p|b' as EL and following as equivalent statements: 'If p ∤ a and p ∤ b, then p ∤ ab' and 'If p ∤ a and p | ab, then p | b'. I assume, in your proof you used an equivalent statement to 'If p ∤ a and p ∤ b, then p ∤ ab'? – user38931 Apr 28 '14 at 16:52
  • @user38931 I added a second proof using that form of EL. – Bill Dubuque Apr 28 '14 at 17:06