# 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

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