# Modular Arithmetic Library

Modular Arithmetic Library in C++

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

Modular Arithmetic Article

•  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: