Number Theory

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.

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 erathostenes 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$

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 logarithms 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. I cover 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 defition 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 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 $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.

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

The erathostenes 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 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++.