Euclids Extended Algorithm 15 and 65

Using Euclids Extended Algorithm:
Calculate x and y in Bézout's Identity
using (15,65)

Bezouts Identity

For 2 numbers a and b and divisor d:
ax + by = d

a math	a	b math	b	d math	d	k math	k
Set to 1	1	Set to 0	0		15
Set to 0	0	Set to 1	1		65	Quotient of 15/65	0
1 - (0 x 0)	1	0 - (0 x 1)	0	Remainder of 15/65	15	Quotient of 65/15	4
0 - (4 x 1)	-4	1 - (4 x 0)	1	Remainder of 65/15	5	Quotient of 15/5	3
1 - (3 x -4)	13	0 - (3 x 1)	-3	Remainder of 15/5	0	Quotient of 5/0	0

Take the last non-zero row for d:

a = -4 and b = 1

ax + by = gcd(a,b)
15x + 65y = gcd(15, 65)
GCF(15, 65) = 5

GCF(15, 65) = 5

What is the Answer?

GCF(15, 65) = 5

How does the Euclids Algorithm and Euclids Extended Algorithm Calculator work?

Given 2 numbers a and b, this calculates the following
1) The Greatest Common Divisor (GCD) using Euclids Algorithm
2) x and y in Bézouts Identity ax + by = d using Euclids Extended Algorithm Extended Euclidean Algorithm
This calculator has 2 inputs.

What 1 formula is used for the Euclids Algorithm and Euclids Extended Algorithm Calculator?

ax + by = d

For more math formulas, check out our Formula Dossier

What 8 concepts are covered in the Euclids Algorithm and Euclids Extended Algorithm Calculator?

algorithm: A process to solve a problem in a set amount of time
equation: a statement declaring two mathematical expressions are equal
euclids algorithm: method for computing the greatest common divisor (GCD) of two numbers
euclids extended algorithm: division algorithm for integers
greatest common factor: largest positive integer dividing a set of integers
identity: an equality that holds true regardless of the values chosen for its variables
quotient: The result of dividing two expressions.
remainder: The portion of a division operation leftover after dividing two integers

Example calculations for the Euclids Algorithm and Euclids Extended Algorithm Calculator

Euclids Algorithm and Euclids Extended Algorithm Calculator Video

Tags:

Add This Calculator To Your Website