Use the Euclidean algorithm to find gcd⁡(1529,14039) and gcd⁡(1529,14038). Then find lcm(1529,14039) using the fact that a⋅b=gcd⁡(a,b)⋅lcm(a,b) for all positive integers a,b?

Question

Use the Euclidean algorithm to find gcd⁡(1529,14039) and gcd⁡(1529,14038). Then find lcm(1529,14039) using the fact that a⋅b=gcd⁡(a,b)⋅lcm(a,b) for all positive integers a,b.

Answer 1

MS Excel also has GCD function...

Per MS Excel, the GCD of the first problem is 139.

the GCD of the second problem is 1, which means 14038 and 1529

are relatively prime

Here's how it's done by hand...iteratively, until

the remainder is ZERO. The last divisor is the GCF

14039/ 1529 = 9 r 278 <--- next divides the remainder into the smaller

1529 / 278 = 5 r 139

278 / 139 = 2 r 0

the last divisor is 139, which is the GCF

Likewise:

14038/1529 = 9 r 277

1529 / 277 = 5 r 144

277/144 = 1 r 133

144/133 = 1 r 11

133/11 = 12 r 1

11/1 = 11 r 0

the last divisor is 1, which is the GCF..

so 14038 and 1529 are relatively prime

a*b = gcd(a,b) * lcm(a,b)

1529 * 14039 = 138 * lcm

1529 * 14039/139 = lcm

154429 = lcm

again, to find it iteratively, finds the

first multiple of 14039 that divides by 1529,

as shown in the following table:

n 14039*n 14038*n/1529

1 14039 9.181818182

2 28078 18.36363636

3 42117 27.54545455

4 56156 36.72727273

5 70195 45.90909091

6 84234 55.09090909

7 98273 64.27272727

8 112312 73.45454545

9 126351 82.63636364

10 140390 91.81818182

11 154429 101

lcm is 154429