9
$\begingroup$

Find integers $ a,b, $ and $ c $ where $ \gcd(a,b,c) = 1 $, but $ \gcd(a,b) \neq 1 $, $ \gcd(a,c) \neq 1 $, and $ \gcd(b,c) \neq 1 $.

I tried so many combinations but I can't find 3 integers that meet these requirements.

I even though $ (0,0,0) $ works, because I tried to convince myself 1 is the first positive integer where 0 has a divisor, because you can't divide by 0. I am not sure if there is a more systematic approach to this.

$\endgroup$
3
  • 6
    $\begingroup$ Hint: Try to imagine venn diagrams of prime factors $\endgroup$
    – basket
    Oct 25 '16 at 4:14
  • $\begingroup$ Thank you. I didn't really want an answer, I wanted a way to try and solve it myself. $\endgroup$
    – JD112
    Oct 25 '16 at 4:16
  • $\begingroup$ No problem. Next time you can explicitly mention hints only $\endgroup$
    – basket
    Oct 25 '16 at 4:17
14
$\begingroup$

Consider $a = 6, b= 10, c = 15$

An easy way to construct these is by considering three prime $2, 3, 5$, then pairwise multiply them.

$\endgroup$
6
  • 1
    $\begingroup$ Thank you very much for including the explanation. That is the "systematic" approach I was looking for :) $\endgroup$
    – JD112
    Oct 25 '16 at 4:18
  • 2
    $\begingroup$ As an exercise try to construct $a, b, c, d$ such that $gcd(a, b, c, d) =1$, but pair-wise and triple-wise has gcd greater than 1. =) $\endgroup$ Oct 25 '16 at 4:20
  • $\begingroup$ a,b,c,d = (6,15,35,10) $\endgroup$
    – JD112
    Oct 25 '16 at 4:25
  • $\begingroup$ Oh shoot, that didn't account for triple wise. heh $\endgroup$
    – JD112
    Oct 25 '16 at 4:26
  • $\begingroup$ Hint: try turning your thinking on its head - rather than thinking about what will make each number share a factor with another number, think about the factors that should be missing (start with the example Jacky Chong gave you, then generalise). $\endgroup$
    – Glen O
    Oct 25 '16 at 7:39
0
$\begingroup$

Choose any three prime numbers $p,q,r$ and create the products $pq,qr,pr$. Each product lacks one of the prime factors, so the largest number that divides all three is $1$, but every pair of products has a factor in common, and hence a gcd greater than $1$. This is a generalization of the rather specific answer given first.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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