0
$\begingroup$

What methods are there to find integers from given GCDs? I need to find the natural numbers a, b, c that satisfy gcd(a,b)=21, gcd(b,c)=21, and gcd(a,c)=819.

I managed to find a set {a=819,b=462,c=819} by some guessing and checking with Mathematica, but I need to be able to do this by hand. I had hoped to reverse engineer some method with a solution and the GCD properties, but so far I'm not having much success. Any help appreciated, thanks.

$\endgroup$
2
  • $\begingroup$ Welcome to Mathematics Stack Exchange. Note that $819=21\times39$. $b=21$ would work too $\endgroup$ Commented Dec 9, 2019 at 22:22
  • 1
    $\begingroup$ Since $819 = 3^2\cdot 7 \cdot 13$, $a$ and $c$ must both be divisible by $819$, and then $b$ must be divisible by $21$. Any values for all three will work as long as there no additional factors of $3$, $7$, or $13$. $\endgroup$
    – rogerl
    Commented Dec 9, 2019 at 22:24

1 Answer 1

1
$\begingroup$

Let $\dfrac aA=\dfrac bB=21$ so that $(A,B)=1$

Similarly $b=21D,c=21C,(D,C)=1$

$\implies B=D,(B,C)=1$

Finally we need $819=(21A,21C)=21(A,C)\implies (A,C)=39$

WLOG $\dfrac Ap=\dfrac Cq=39,$ so that $(p,q)=1$

$(B,39p)=(B,39q)=(p,q)=1$

where $b=21B,a=21A=819p,c=819q$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .