This library provides the basics of modular arithmetic operations:

- Great Common Divisor (GCD)
- Least Common Multiple (LCM)
- Bezout solver
- Decomposition number algorithm
- Euler’s totient function
- Primality Test
- Find next Prime
- Inverse function
- Solver for 1 equation
- Solver for multiple equations

###### -GitHub repository:

Modular Arithmetic Source Code

###### -Article

#### BASICS

- Reflexibity
- Simmetry
- Transivity

if ,,

then:

- )

#### Great Common Divisor (GCD)

Euclides Algorithm is used to solve this problem.

#### Least Common Multiple (LCM)

We can calculate the LCM using GCD:

#### Bezout’s Theorem

Using Euclides Algorithm we are able to find and, where:

#### Number Decomposition

This algorithm could be optimized because we only need to look numbers

below , and thus, the time is reduced.

#### a^b(mod m)

we are not always to compute high numbers with big exponents, and

hence we need another way that simplifies:

we write b in binary, such as: ,

where is 0 or 1.

and

#### Primality Test

This algorithm tells you, whether a number is prime or not (optimized).

#### Find next Prime

This function is important in cryptography. It uses an initial number and finds the next prime over the number given.

#### Euler’s Totient Function

We need the number decomposition algorithm mentioned before.

#### Linear Equation Solver

To solve the equation, we divide by

We use Bezout:

Then, we multiply by :

There are solutions for this equation

\section{Inverse}

The inverse of a number in mod m is calculated using the linear solver:

#### System of Equations

Solving a system of equations is done by constantly solving two equations.

, where and are the solutions

for each equation.

We repeat the process: