Extended Euclidean Calculator
Basic Calculator
Advanced Calculator
Enter the required details to calculate the greatest common divisor (GCD) and the coefficients of the Extended Euclidean Algorithm
First Number (a)
Second Number (b)
GCD (a, b)
Coefficients (x, y)
First Number (a) Second Number (b) GCD (a, b) Coefficients (x, y)
Calculate
Reset
function showBasic() {
document.getElementById("basicCalculator").style.display = 'block';
document.getElementById("advancedCalculator").style.display = 'none';
}
function showAdvanced() {
document.getElementById("advancedCalculator").style.display = 'block';
document.getElementById("basicCalculator").style.display = 'none';
}
function calculate() {
if (document.getElementById("basicCalculator").style.display !== 'none') {
const a = parseInt(document.getElementById("number1").value);
const b = parseInt(document.getElementById("number2").value);
if (!isNaN(a) && !isNaN(b)) {
const gcdResult = gcd(a, b);
const coefficients = extendedEuclidean(a, b);
document.getElementById("gcdResult").value = gcdResult;
document.getElementById("coefficients").value = `(${coefficients.x}, ${coefficients.y})`;
} else {
alert("Please fill in all fields to calculate the GCD and coefficients.");
}
} else {
const a = parseInt(document.getElementById("extendedNumber1").value);
const b = parseInt(document.getElementById("extendedNumber2").value);
if (!isNaN(a) && !isNaN(b)) {
const gcdResult = gcd(a, b);
const coefficients = extendedEuclidean(a, b);
document.getElementById("extendedGcdResult").value = gcdResult;
document.getElementById("extendedCoefficients").value = `(${coefficients.x}, ${coefficients.y})`;
} else {
alert("Fill in all fields to calculate the GCD and coefficients.");
}
}
}
function resetFields() {
document.getElementById("number1").value = '';
document.getElementById("number2").value = '';
document.getElementById("gcdResult").value = '';
document.getElementById("coefficients").value = '';
document.getElementById("extendedNumber1").value = '';
document.getElementById("extendedNumber2").value = '';
document.getElementById("extendedGcdResult").value = '';
document.getElementById("extendedCoefficients").value = '';
}
function gcd(a, b) {
if (b === 0) {
return a;
} else {
return gcd(b, a % b);
}
}
function extendedEuclidean(a, b) {
if (b === 0) {
return { x: 1, y: 0 };
} else {
const { x: x1, y: y1 } = extendedEuclidean(b, a % b);
const x = y1;
const y = x1 - Math.floor(a / b) * y1;
return { x, y };
}
}
.styled-input {
border: 2px solid #0093da;
border-radius: 5px;
padding: 10px;
box-shadow: inset 0 1px 2px rgba(0,0,0,0.1);
background-color: #fff;
transition: all 0.3s ease;
}
.styled-input:focus {
border-color: #007bb5;
box-shadow: 0 0 5px rgba(0, 115, 175, 0.5);
outline: none;
}
Enter two integers into the calculator to determine their greatest common divisor (GCD) and the coefficients of the Extended Euclidean Algorithm.
Extended Euclidean Algorithm Explanation
The Extended Euclidean Algorithm is an extension of the Euclidean Algorithm, which is used to find the greatest common divisor (GCD) of two integers. The Extended Euclidean Algorithm not only computes the GCD of two integers a and b, but also finds the coefficients x and y such that:
a * x + b * y = gcd(a, b)
These coefficients (x and y) are useful in many areas of number theory, including solving Diophantine equations and computing modular inverses.
Understanding the Algorithm
The Euclidean Algorithm for finding the GCD of two integers a and b (with a > b) is based on the principle that the GCD of a and b is the same as the GCD of b and a % b (the remainder of the division of a by b). The process is repeated until