Euclidean Algorithm

There's a total of 3 articles.




Divisibility

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.
Me
Published on Sun, May 21, 2017
Last modified on Sun, Jun 16, 2024
1056 words - Page Source

Extended Euclidean Algorithm

Extended Euclidean Algorithm
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.
Me
Published on Tue, Jun 2, 2015
Last modified on Sun, Jun 16, 2024
814 words - Page Source

Euclidean Algorithm

Euclidean Algorithm
The euclidean algorithm finds the greatest common divisor of two numbers. In this article I implement the algorithm from scratch in C++.
Me
Published on Mon, Jun 1, 2015
Last modified on Sun, Jun 16, 2024
425 words - Page Source