Modular arithmetic

Set an integer n>1, we will refer to it as the module. Recall that any integer b can be written in a single form as

where 0\leq r < n the number r is called the remainder.

We say that a and b are congruent modulo n if they verify either of the two equivalent statements.

• a and b give the same remainder when dividing by n.
• The difference between a and b is a multiple of n, i.e.(a-b)\in n\Z.we write in that case a\equiv b (mod n)

NOTES When, for context, it is not necessary to specify the module we will simply write a\equiv b note that given a\in Z, we denote by \bar{a} the remainder of dividing a by n. the set { \lbrace\bar{0},\bar{1},...,\overline{n-1}} \rbrace of all posible residues is denoted \Z/n\Z using this notation, it is the same to write(for example if we work module 4) \bar{7}=\bar{3} or 7\equiv 4 Both expressions have the same meaning

Euclid's algorithm

This is a way to find the d.c.m. between two integers. Moreover, it allows to write this d.c.m. as a linear combination (with integer coefficients) of these. For example, let us calculate the d.c.m. between a = 236441 and b = 45955. We consider the pair (236411, 45955) We divide the larger by the smaller, obtaining.

We then temporarily forget about the larger number, and keep the remainder as the new number. That is, we pass to the pair (45955, 6666). We perform the same operation again, dividing the small by the large, consider the new pair formed by the previous small and by the remainder:

Terminate the process when it reaches a zero residue. The above residue is the m.c.d. i.e. m.c.d.(236411, 45955) = 2.