Using Euclids Extended Algorithm:
Calculate x and y in Bézout's Identity
using (11,85)
Bezouts Identity
For 2 numbers a and b and divisor d:
ax + by = d
Extended Algorithm Table
| a math | a | b math | b | d math | d | k math | k |
|---|---|---|---|---|---|---|---|
| Set to 1 | 1 | Set to 0 | 0 | 11 | |||
| Set to 0 | 0 | Set to 1 | 1 | 85 | Quotient of 11/85 | 0 | |
| 1 - (0 x 0) | 1 | 0 - (0 x 1) | 0 | Remainder of 11/85 | 11 | Quotient of 85/11 | 7 |
| 0 - (7 x 1) | -7 | 1 - (7 x 0) | 1 | Remainder of 85/11 | 8 | Quotient of 11/8 | 1 |
| 1 - (1 x -7) | 8 | 0 - (1 x 1) | -1 | Remainder of 11/8 | 3 | Quotient of 8/3 | 2 |
| -7 - (2 x 8) | -23 | 1 - (2 x -1) | 3 | Remainder of 8/3 | 2 | Quotient of 3/2 | 1 |
| 8 - (1 x -23) | 31 | -1 - (1 x 3) | -4 | Remainder of 3/2 | 1 | Quotient of 2/1 | 2 |
| -23 - (2 x 31) | -85 | 3 - (2 x -4) | 11 | Remainder of 2/1 | 0 | Quotient of 1/0 | 0 |
Take the last non-zero row for d:
a = 31 and b = -4
GCD Equation
ax + by = gcd(a,b)
11x + 85y = gcd(11
Final Answer:
GCF(11, 85) = 1
What is the Answer?
GCF(11, 85) = 1
How does the Euclids Algorithm and Euclids Extended Algorithm Calculator work?
Free Euclids Algorithm and Euclids Extended Algorithm Calculator - 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.
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
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
