Mathematical AlgorithmsIntermediate

Extended Euclidean Algorithm

Extends the Euclidean algorithm to find integers x and y satisfying Bézout's identity: ax + by = GCD(a, b). Not only computes GCD but also finds the coefficients of linear combinations. Fundamental to modular arithmetic, RSA cryptography, and solving linear Diophantine equations.

#mathematical#number-theory#cryptography#modular-arithmetic

Complexity Analysis

Time (Average)

O(log min(a, b))

Expected case performance

Space

O(1)

Memory requirements

Time (Best)

O(log min(a, b))

Best case performance

Time (Worst)

O(log min(a, b))

Worst case performance

Input Numbers (positive integers)

Number A

Number B

Quick Presets:

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Mathematical Algorithms

Sieve of Eratosthenes

Beginner

Find all prime numbers up to n by iteratively marking composites. Named after Eratosthenes of Cyrene (c. 276-194 BC).

O(n log log n)

O(n)

mathematicalprime-numbers

Start Learning

Pascal's Triangle

Beginner

Triangular array of binomial coefficients where each number is the sum of the two numbers directly above it. Named after Blaise Pascal (1623-1662), though known to mathematicians centuries earlier. Demonstrates beautiful mathematical patterns including binomial expansion, combinatorics, and connections to Fibonacci numbers.

O(n²)

mathematicalcombinatorics

Start Learning

Euclidean Algorithm (GCD)

Beginner

Ancient algorithm from around 300 BC that efficiently computes the greatest common divisor of two integers. Based on the principle that GCD(a, b) = GCD(b, a mod b). One of the oldest algorithms in continuous use, forming the foundation of number theory, cryptography, and fraction simplification.

O(log min(a, b))

O(1)

mathematicalnumber-theory

Start Learning

Back to Mathematical Algorithms