Number Theory

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.

Integer factorization is the process of decomposing a *composite* number into a product of smaller integers, if these integers are restricted to be prime numbers then the process is called **prime factorization**. This article covers factorization using trial division and fermat factorization through Pollard's Rho algorithm and using the sieve of eratosthenes.

The divisor function returns the number of divisors of an integer. This article covers important relations of the divisor function and prime numbers.

A prime number is a natural number greater than $1$ which has no positive divisors other than $1$ and itself. This article covers different algorithms for checking if a number is prime or not, including a naive test, the Eratosthenes Sieve, the Euler Primality Test, and the Miller-Rabin Primality Test.

This article describes and implements a solution for the following problem: given two numbers $n$ and $k$ find the greatest power of $k$ that divides $n!$

Let $n!_{\\%p}$ be a special factorial where $n!$ is divided by the maximum exponent of $p$ that divides $n!$. This article describes this problem and its solution, with an implementation in C++.

The discrete logarithm finds a solution for $x$ in the congruence $a^x \equiv b \pmod{n}$ where $a$, $b$, and $n$ are **integers**, $a$ and $n$ are coprime. This article covers two algorithms to solve this problem: by trial multiplication and using Baby Step Giant Step.

The Chinese Remainder Theorem (CRT) is a theorem that deals with finding a solution to a system of congruences. This article covers the definition of the CRT and an example implementation in C++.

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.

Given two numbers $a$ and $n$, finding $a^n$ involves performing $n$ multiplications of $a$. However, it's possible to do this in $log(n)$ operations using binary exponentiation.

The Eratosthenes Sieve is an algorithm to find prime numbers up to a positive number $n$ using $O(n)$ space.

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

*Euler's phi function* represented as $\phi(n)$ gives, for a number $n$, the number of coprimes in the range $[1..n]$; in other words, the quantity of numbers in the range $[1..n]$ whose greatest common divisor with $n$ is the unity. In this article, I try to explain how it works and implement it in C++.