Author Jonathan David For my fiction, visit AuthorJonD.com
Author Jonathan David
Math Monthly

Using the Euclidean Algorithm to Find the Greatest Common Divisor – Number Theory Example

by |Published

Using the Euclidean Algorithm to Find the Greatest Common Divisor – Number Theory Example

This lesson is nothing more than a free preview of The Ultimate Crash Course for STEM Majors. This number theory example demonstrates how to use the Euclidean Algorithm to find the greatest common divisor of 875 and 4075 by identifying the successive quotients and remainders.

Explore The Ultimate Crash Course for STEM Majors

I also write fiction. Visit AuthorJond.com to explore my fiction, books, stories, and other writing.

Question 1.

Use the Euclidean Algorithm to find the greatest common divisor of 875 and 4075.

Theorem 3. The Euclidean Algorithm. If $a$ and $b$ are positive integers, $b\neq 0$, and

$$a=bq+r,\qquad 0\leq r$$
$$b=rq_1+r_1,\qquad 0\leq r_1$$
$$r=r_1q_2+r_2,\qquad 0\leq r_2$$
$$\vdots$$
$$r_k=r_{k+1}q_{k+2}+r_{k+2},\qquad 0\leq r_{k+2}$$

then for $k$ large enough, say $k=t$, we have

$$r_{t-1}=r_tq_{t+1}$$

and $(a,b)=r_t$.

Let $a=4075,\ b=875$.

Then,

$$4075=(875)(4)+(4075-4(875))$$
$$=4(875)+575$$
$$\Rightarrow a=4075,\qquad b=875,\qquad q=4,\qquad r=575$$

Then,

$$875=(575)(1)+(875-(1)575)$$
$$=(575)(1)+300$$
$$\Rightarrow b=875,\qquad r=575,\qquad q_1=1,\qquad r_1=300$$

Then,

$$575=(300)(1)+(575-(1)(300))$$
$$=(300)(1)+275$$
$$\Rightarrow r=575,\qquad r_1=300,\qquad q_2=1,\qquad r_2=275$$

Then,

$$300=275(1)+(300-(1)(275))$$
$$=275(1)+25$$
$$\Rightarrow r_1=300,\qquad r_2=275,\qquad q_3=1,\qquad r_3=25$$

Then,

$$300=25(12)+0$$

By The Euclidean Algorithm, $r_3=r_t=25$.

Thus,

$$\gcd(875,4075)=25$$

For Q2

$$4075=(875)(4)+575$$
$$875=(575)(1)+300$$
$$575=(300)(1)+275$$
$$300=275(1)+25$$
$$300=25(12)+0$$

Question 2. Use your solution from Question 1 to find integers $x$ and $y$ such that $875x+4075y=50$.

Theorem 4. If $(a,b)=d$, then there are integers $x$ and $y$ such that

$$ax+by=d$$

From Q1

$$4075=4(875)+575$$
$$875=(575)(1)+300$$
$$575=(300)(1)+275$$
$$300=275(1)+25$$
$$300=25(12)+0$$

It is suggested to work ‘The Euclidean Algorithm’ backwards.

Then,

$$300=25(12)+0$$
$$\Rightarrow 300=275(1)+25$$
$$\Rightarrow 300-275(1)=25$$
$$\Rightarrow [875-(575)(1)]-[575-(300)(1)]=25$$
$$\Rightarrow [875-(575)(1)]-[(4075-(4)(875))-(300)(1)]=25$$

[Note* Get all terms to be original terms 875, 4075]

$$\Rightarrow [875-(575)(1)]-[(4075-(4)(875))-(875-(575)(1))]=25$$
$$\Rightarrow 875-(575)(1)-(4075-(4)(875))+(875-(575)(1))=25$$
$$\Rightarrow 875-(575)(1)-4075+(4)(875)+875-(575)(1)=25$$
$$\Rightarrow {\color{magenta}{-4075+(6)(875)}}-(575)(2)=25$$
$$\Rightarrow -4075+(6)(875)-(4075-(4)(875))(2)=25$$
$$\Rightarrow -4075+(6)(875)-4075(2)+(8)(875)=25$$
$$\Rightarrow (14)(875)+4075(-3)=25$$
$$\Rightarrow (875)(28)+4075(-6)=50$$
$$\therefore x=28,\qquad y=-6$$

Question 3.

Continue The Ultimate Crash Course for STEM Majors

What you just read is nothing more than a free preview of The Ultimate Crash Course for STEM Majors. The complete Crash Course series contains additional worked examples covering the Euclidean Algorithm, greatest common divisors, number theory, algebra, calculus, differential equations, mathematics, physics, engineering, and other STEM subjects.

Get The Ultimate Crash Course for STEM Majors

I Write Fiction Too

If you enjoy my educational work and want to explore something completely different, visit AuthorJond.com to check out my fiction, books, stories, and other writing.

You may also like

Leave a comment