Question

Compute the GCD of 128 and 96 using Euclidean Division Method.​

Answer 1

Please see the description image

Answer 2

$\displaystyle\huge\red{\underline{\underline{Solution}}}$

FORMULA TO BE IMPLEMENTED

THE DIVISION ALGORITHM

If a and b are integers where b is a positive integer then there exist unique integers q and r such that

$\sf{a = bq + r} \: \: \: \: with \: \: 0 \leqslant r < b$

LEMMA

If m and n are two positive integers and

$\sf{ \: m = nq +r \: , \: \: 0 \leqslant r < n \: then \: gcd(m,n) = gcd(n,r) }$

TO DETERMINE

The GCD of 128 and 96 using Euclidean Division Method.

CALCULATION

$\sf{ \: \: \: \: \: 128 = 1 \times 96 + 32}$

$\sf{ \: \: \: \: \: 96 = 3\times 32 + 0}$

$\sf{Hence \: \: gcd ( 128, 96) =32}$

Also

$\sf{ \: \: \: 32 = 128 - 96 \: \: }$

$\implies \: \sf{ \: \: \: 32 = 1 \times 128 + ( - 1) \times 96 \: \: }$