# Euclids Extended Algorithm 15 and 65

## Enter Number

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 mathab mathbd mathdk mathk
Set to 11 Set to 0015
Set to 00 Set to 1165Quotient of 15/650
1 - (0 x 0)10 - (0 x 1)0Remainder of 15/6515Quotient of 65/154
0 - (4 x 1)-41 - (4 x 0)1Remainder of 65/155Quotient of 15/53
1 - (3 x -4)130 - (3 x 1)-3Remainder of 15/50Quotient of 5/00

## 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

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?

1. 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