Euclidean Algorithm
There's a total of 3 articles.
Divisibility
Let $a,b \in \mathbb{Z}$, we say that $a$ divides $b$, written $a \given b$, if there’s an integer $n$ so that: $b = na$. If $a$ divides $b$ then $b$ is divisible by $a$ and $a$ is a divisor or factor of $b$, also $b$ is called a multiple of $a$.
This article covers the greatest common divisor and how to find it using the euclidean algorithm, the extended euclidean algorithm to find solutions to the equation $ax + by = gcd(a, b)$ where $a, b$ are unknowns.
Extended Euclidean Algorithm
math
number theory
divisibility
modulo
linear congruence equations
mudular multiplicative inverse
extended euclidean algorithm
euclidean algorithm
diophantine equations
The extended euclidean algorithm finds solutions to the equation $ax + by = gcd(a, b)$
where $a, b$ are unknowns. This article covers a few applications of the extended euclidean algorithm
like finding the modular multiplicative inverse of a number, and finding solutions for
linear congruence equations.
Euclidean Algorithm
The euclidean algorithm finds the greatest common divisor of two numbers. In this article
I implement the algorithm from scratch in C++.