There's a total of 14 articles.

### Divisibility → Read more...

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

*by $a$ and $a$ is a*

**divisible***of $b$, also $b$ is called a*

**divisor or factor***of $a$.*

**multiple**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 → Read more...

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.

### Divisor Function → Read more...

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

### Primality Test → Read more...

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.

### Prime factors of a factorial → Read more...

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

### Special factorial modulo p → Read more...

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

### Discrete Logarithm → Read more...

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.

### Chinese Remainder Theorem → Read more...

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 → Read more...

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.

### Extended Euclidean Algorithm → Read more...

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.

### Binary Exponentiation → Read more...

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.

### Erathostenes Sieve → Read more...

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

### Euclidean Algorithm → Read more...

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 → Read more...

*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++.