Question

How many divisions are required to find gcd(144, 233) using the Euclidean algorithm?

Short answer

12divisions are required to find gcd(144, 233)

Step-by-step solution

Step 1

Definitions

Division theorem let be an integer and b a positive integer. Then there are unique integers qand r with 0 < r < bsuch that a = qb + r

q Is called the quotient and is called the remainder.

q = a div b

r = a mod b

Step 2

Solution

gcd (144,233)

To determine gcd (a,b), we let c = a mod b .we returnb if c = 0and we return gcd (b,c)if c = 0

$\begin{array}{r}\mathbf{144}\mathbf{mod}\mathbf{233}\mathbf{=}\mathbf{144}\mathbf{\Rightarrow }\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{233}\mathbf{,}\mathbf{144}\mathbf{)}\\ \mathbf{233}\mathbf{mod}\mathbf{144}\mathbf{=}\mathbf{89}\mathbf{\Rightarrow }\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{89}\mathbf{)}\\ \mathbf{144}\mathbf{mod}\mathbf{89}\mathbf{=}\mathbf{55}\mathbf{\Rightarrow }\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{89}\mathbf{,}\mathbf{85}\mathbf{)}\\ \mathbf{89}\mathbf{mod}\mathbf{55}\mathbf{=}\mathbf{34}\mathbf{\Rightarrow }\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{55}\mathbf{,}\mathbf{34}\mathbf{)}\\ \mathbf{55}\mathbf{mod}\mathbf{34}\mathbf{=}\mathbf{21}\mathbf{\Rightarrow }\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{34}\mathbf{,}\mathbf{21}\mathbf{)}\\ \mathbf{34}\mathbf{mod}\mathbf{21}\mathbf{=}\mathbf{13}\mathbf{\Rightarrow }\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{21}\mathbf{,}\mathbf{13}\mathbf{)}\\ \mathbf{21}\mathbf{mod}\mathbf{13}\mathbf{=}\mathbf{8}\mathbf{\Rightarrow }\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{13}\mathbf{,}\mathbf{8}\mathbf{)}\\ \mathbf{13}\mathbf{mod}\mathbf{8}\mathbf{=}\mathbf{5}\mathbf{\Rightarrow }\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{8}\mathbf{,}\mathbf{5}\mathbf{)}\\ \mathbf{8}\mathbf{mod}\mathbf{5}\mathbf{=}\mathbf{3}\mathbf{\Rightarrow }\mathbf{agcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{5}\mathbf{,}\mathbf{3}\mathbf{)}\\ \mathbf{5}\mathbf{mod}\mathbf{3}\mathbf{=}\mathbf{2}\mathbf{\Rightarrow }\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{3}\mathbf{,}\mathbf{2}\mathbf{)}\\ \mathbf{3}\mathbf{mod}\mathbf{2}\mathbf{=}\mathbf{1}\mathbf{\Rightarrow }\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{2}\mathbf{,}\mathbf{1}\mathbf{)}\\ \mathbf{2}\mathbf{mod}\mathbf{1}\mathbf{=}\mathbf{0}\mathbf{\Rightarrow }\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{144}\mathbf{,}\mathbf{233}\mathbf{)}\mathbf{=}\mathbf{1}\end{array}$

Thus, we then obtained gcd(144, 233) divisions