# Modular arithmetic (clock arithmetic)

Modular arithmetic is a system of arithmetic for integers, where values reset to zero and begin to increase again, after reaching a certain predefined value, called the modulus (modulo). Modular arithmetic is widely used in computer science and cryptography.

_{N}be a set of all non-negative integers that are smaller than N:

Z

_{N}= {0,1,2,...,N-1}

- N is a positive integer,
- if N is a prime, it will be denoted p (and the whole set as Z
_{p}).

To determine the value of an integer for a modulus N, one should divide this number by N. Its value in Z_{N} is equal to the remainder of the division. In modular arithmetic, it is possible to define all typical operations, as in normal arithmetic. They work as one may expect. It is possible to use the same commutative, associative, and distributive laws.

## Modular inversion

Integers in modular arithmetic may (but not must) have inverse numbers.

_{N}is a number y in Z

_{N}, that satisfies the equation:

x · y = 1 (in Z

_{N})

- y is denoted x
^{-1}

For example, if N is an odd number, then the inverse of 2 in Z_{N} is (N+1)/2:

x · (N+1)/2 = N + 1 = 1 (in Z_{N})

_{N}if and only if the numbers x and N are relatively prime.

- The theorem can be proved using the fact that it is possible to present the greatest common divisor of two integers as a sum of two products each of the numbers and another properly selected integer:

a·x + b·y = gcd(x,y)

Determining inverse numbers in Z_{N} allows solving linear equations in modular arithmetic:

the equation: a · x + b = 0 (in Z_{N})

has the solution: x = -b · a^{-1} (in Z_{N})

^{*}

_{N}denotes a set of all elements of Z

_{N}that are invertible in Z

_{N}; that means the set of numbers x that belong to Z

_{N}, and x and N are relatively prime.

- for example for a prime number p:

Z^{*}_{p}= Z_{p}\ {0} = {1, 2, …, p - 1}

## Calculating inverse numbers in Z_{N}

Inverse numbers in Z_{N} can be determined in time O(log_{2}N) using the Euclidean algorithm, which allows to compute the greatest common divisor of two integers.

Extended Euclidean algorithm finds the coefficients of Bézout's identity, that are integer numbers a and b such that:

a·x + b·y = gcd(x,y)

In order to receive the inverse number, one should perform the following transformations:

a·x + b·y = 1

b·y = 1 (in Z_{a})

Thus, b is the inverse number of y in Z_{a}.

The numbers a and b should be calculated during each step of the Euclidean algorithm, using the received values of those numbers in previous steps and the quotients:

a_{i} = a_{i-2} - q_{i-1}·a_{i-1}

b_{i} = b_{i-2} - q_{i-1}·b_{i-1}

If algorithm's steps are numbered from 1, one should assume the following initial values of the coefficients:

a_{-1} = 1

a_{0} = 0

b_{-1} = 0

b_{0} = 1

The final values of the coefficients a and b are received in the same step when the greatest common divisor of x and y is calculated (thus, in the step with the last non-zero remainder).