greatest common divisor [imath]\bold{vs}[/imath] least common multiple

[logistic_guy]

For each of the following pairs of integers \(\displaystyle a\) and \(\displaystyle b\), determine their greatest common divisor, their least common multiple, and write their greatest common divisor in the form \(\displaystyle ax + by\) for some integers \(\displaystyle x\) and \(\displaystyle y\).

\(\displaystyle \bold{(a)} \ a = 20, b = 13\)
\(\displaystyle \bold{(b)} \ a = 69, b = 372\)
\(\displaystyle \bold{(c)} \ a = 792, b = 275\)
\(\displaystyle \bold{(d)} \ a = 11391, b = 5673\)
\(\displaystyle \bold{(e)} \ a =1761, b = 1567\)
\(\displaystyle \bold{(f)} \ a = 507885, b = 60808\)

 

[logistic_guy]

\(\displaystyle \bold{(a)}\)

\(\displaystyle 20 \rightarrow 1 \times 2 \times 2 \times 5\)
\(\displaystyle 13 \rightarrow 1 \times 13\)

Then,

\(\displaystyle \text{gcd}(20,13) = \textcolor{blue}{1}\)
\(\displaystyle \text{lcm}(20,13) = \frac{20 \times 13}{\text{gcd}(20,13)} = \frac{260}{1} = \textcolor{blue}{260}\)

\(\displaystyle \text{gcd}(20,13) = \textcolor{blue}{20(2) - 13(3)}\)

 

[logistic_guy]

\(\displaystyle \bold{(b)}\)

\(\displaystyle 69 = 1 \times 3 \times 23\)
\(\displaystyle 372 = 1 \times 2 \times 2 \times 3 \times 31\)

Then,

\(\displaystyle \text{gcd}(69,372) = \textcolor{blue}{3}\)
\(\displaystyle \text{lcm}(69,372) = \frac{69 \times 372}{\text{gcd}(69,372)} = \frac{25668}{3} = \textcolor{blue}{8556}\)

\(\displaystyle \text{gcd}(69,372) = \textcolor{blue}{69(27) - 372(5)}\)

 

[logistic_guy]

\(\displaystyle \bold{(c)}\)

In the last two posts I did not show how I got \(\displaystyle \text{gcd}(a,b) = ax + by\). In this post, I will show in details how to find these two integers \(\displaystyle x\) and \(\displaystyle y\). Since the solution \(\displaystyle \text{gcd}(a,b) = ax + by\) is not unique, there are many integers of \(\displaystyle x\) and \(\displaystyle y\) that satisfy this equation. So I will show in general how to find them. I will also solve the \(\displaystyle \text{gcd}(a,b)\) this time by the \(\displaystyle \textcolor{red}{\text{Euclidean algorithm}}\).

Let us begin the game.



\(\displaystyle 792 = (2)275 + 242\)
\(\displaystyle 275 = (1)242 + 33\)
\(\displaystyle 242 = (7)33 + 11\)
\(\displaystyle 33 = (3)11\)

\(\displaystyle \text{gcd}(792,275) = \textcolor{blue}{11}\)
\(\displaystyle \text{lcm}(792,275) = \frac{792 \times 275}{\text{gcd}(792,275)} = \frac{198000}{11} = \textcolor{blue}{19800}\)

Here is how to find: \(\displaystyle \text{gcd}(792,275) = 792x + 275y\)

Look at the Euclidean algorithm above and try to write it in reverse!

Starting at:

\(\displaystyle 11 = 242 - (7)33\)
\(\displaystyle 11 = 242 - (7)[275 - (1)242]\)
\(\displaystyle 11 = (8)242 - (7)275\)
\(\displaystyle 11 = (8)[792 - (2)275] - (7)275\)
\(\displaystyle 11 = (8)792 - (23)275\)

This gives:

\(\displaystyle \text{gcd}(792,275) = \textcolor{blue}{792(8) - 275(23)}\)

Or in general:

\(\displaystyle x = x_0 + \frac{b}{\text{gcd}(a,b)}t\)

\(\displaystyle y = y_0 - \frac{a}{\text{gcd}(a,b)}t\)

where \(\displaystyle x_0\) and \(\displaystyle y_0\) is one solution you got from the reverse Euclidean algorithm and \(\displaystyle t\) is any integer. In this case, \(\displaystyle x_0 = 8\) and \(\displaystyle y_0 = -23\).

Let us try to find another solution.

\(\displaystyle x = 8 + \frac{275}{11}(1) = 33\)

\(\displaystyle y = -23 - \frac{792}{11}(1) = -95\)

Therefore,

\(\displaystyle \text{gcd}(792,275) = \textcolor{green}{792(33) - 275(95)}\)

 

[logistic_guy]

\(\displaystyle \bold{(d)}\)

\(\displaystyle 11391 = (2)5673 + 45\)
\(\displaystyle 5673 = (126)45 + 3\)
\(\displaystyle 45 = (15)3\)

\(\displaystyle \text{gcd}(11391,5673) = \textcolor{blue}{3}\)
\(\displaystyle \text{lcm}(11391,5673) = \frac{11391 \times 5673}{\text{gcd}(11391,5673)} = \frac{64621143}{3} = \textcolor{blue}{21540381}\)

\(\displaystyle 3 = 5673 - (126)45\)
\(\displaystyle 3 = 5673 - (126)[11391 - (2)5673]\)
\(\displaystyle 3 = (253)5673 - (126)11391\)

\(\displaystyle \text{gcd}(11391,5673) = \textcolor{blue}{-11391(126) + 5673(253)}\)

 

[logistic_guy]

\(\displaystyle \bold{(e)}\)

\(\displaystyle 1761 = (1)1567 + 194\)
\(\displaystyle 1567 = (8)194 + 15\)
\(\displaystyle 194 = (12)15 + 14\)
\(\displaystyle 15 = (1)14 + 1\)
\(\displaystyle 14 = (14)1\)

\(\displaystyle \text{gcd}(1761,1567) = \textcolor{blue}{1}\)
\(\displaystyle \text{lcm}(1761,1567) = \frac{1761 \times 1567}{\text{gcd}(1761,1567)} = \frac{2759487}{1} = \textcolor{blue}{2759487}\)

\(\displaystyle 1 = 15 - (1)14\)
\(\displaystyle 1 = 15 - (1)[194 - (12)15]\)
\(\displaystyle 1 = (13)15 - (1)194\)
\(\displaystyle 1 = (13)[1567 - (8)194] - (1)194\)
\(\displaystyle 1 = (13)1567 - (105)194\)
\(\displaystyle 1 = (13)1567 - (105)[1761 - (1)1567]\)
\(\displaystyle 1 = (118)1567 - (105)1761\)

\(\displaystyle \text{gcd}(1761,1567) = \textcolor{blue}{-1761(105) + 1567(118)}\)

 

[logistic_guy]

\(\displaystyle \bold{(f)}\)

\(\displaystyle 507885 = (8)60808 + 21421\)
\(\displaystyle 60808 = (2)21421 + 17966\)
\(\displaystyle 21421 = (1)17966 + 3455\)
\(\displaystyle 17966 = (5)3455 + 691\)
\(\displaystyle 3455 = (5)691\)

\(\displaystyle \text{gcd}(507885,60808) = \textcolor{blue}{691}\)
\(\displaystyle \text{lcm}(507885,60808) = \frac{507885 \times 60808}{\text{gcd}(507885,60808)} = \frac{30883471080}{691} = \textcolor{blue}{44693880}\)

\(\displaystyle 691 = 17966 - (5)3455\)
\(\displaystyle 691 = 17966 - (5)[21421 - (1)17966]\)
\(\displaystyle 691 = (6)17966 - (5)21421\)
\(\displaystyle 691 = (6)[60808 - (2)21421] - (5)21421\)
\(\displaystyle 691 = (6)60808 - (17)21421\)
\(\displaystyle 691 = (6)60808 - (17)[507885 - (8)60808]\)
\(\displaystyle 691 = (142)60808 - (17)507885\)

\(\displaystyle \text{gcd}(507885,60808) = \textcolor{blue}{-507885(17) + 60808(142)}\)