math-advanced-euclidean-algorithm.html
* created: 2025-11-29T20:35
* modified: 2025-11-29T23:01
title
Advaced Euclidean Algorithm
description
Used to calculate the $gcd(a, n)$ and the multiplicative inverse of $a$, with $a \in \mathbb{Z}^{*}_{n}$
Advanced Euclidean Algorithm
Used to calculate the gcd(a, n) and the multiplicative inverse of a \mod n, with a \in \mathbb{Z}^{*}_{n}, meaning, it calculates both s and t, for the values a and n:
gcd(a,n)= n \cdot s + a \cdot t
For n = 73 and a = 56 we get:
|
\cdot 73 |
\cdot 56 |
q |
|
| 73 \; (n) |
1 |
0 |
|
73 = 1 \cdot 73 + 0 \cdot 56 |
| 56 \; (a) |
0 |
1 |
1 |
56 = 0 \cdot 73 + 1 \cdot 56 |
| 17 |
1 |
-1 |
3 |
17 = 1 \cdot 73 - 1 \cdot 56 |
| 5 |
-3 |
4 |
3 |
5 = -3 \cdot 73 + 4 \cdot 56 |
| 2 |
10 |
-13 |
2 |
2 = 10 \cdot 73 - 13 \cdot 56 |
| 1 |
-23 |
30 |
2 |
1 = -23 \cdot 73 + 30 \cdot 56 |
| 0 |
|
|
|
|
The gcd(73, 56) = 1 and the multiplicative inverse of a is 30, because: 1 \equiv -23 \cdot 73 + 30 \cdot 56 \pmod{73}