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$ – J. W. Tanner Dec 9 '19 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 Dec 9 '19 at 22:24
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$

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.