Modulo

Let $a,b \in \mathbb{Z}$. We say that $a$ _**divides**_ $b$, written $a \given b$, if there's an integer $n$ such 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 $x, y$ are unknowns.

Modular arithmetic is a type of arithmetic that deals with integers and remains within a fixed range of values. It involves performing arithmetic operations such as addition, subtraction, multiplication, and division, but with the added concept of a "modulus" or a "mod" value. This article covers the definition of a congruence relation, and some of its properties like addition, multiplication, exponentiation, and inverse. Next, I show how we can use the Extended Euclidean Algorithm to find the modular multiplicative inverse in a general case and in the case of coprime numbers.

The Extended Euclidean Algorithm finds solutions to the equation $ax + by = gcd(a, b)$ where $x, y$ 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.

The Euclidean Algorithm finds the greatest common divisor of two numbers. In this article I implement the algorithm from scratch in C++.