Modular Arithmetic

In this lesson, we'll talk about some definitions and properties about Modular Arithmetic.

Since this topic is related to Number Theory, we'll only talk about integers numbers in this lesson.

Let's first define what's the modulo operation, which we'll use the operator . Given and (), is equal to the remainder of the division of by . For example, and . We can extract a simple (but very useful) formula from its definition: . This formula is based in the Euclidian Division of by .

Although this operation is simple, it is widely used in mathematics and in competitive programming. For example, in mathematics it is used in congruence (we will see what this is next). In competitive programming, it is used for example in problems that have very large answers, which could cause an overflow in the variables. Usually, they ask us to print out this answer modulo some number.

Now, let's talk about congruences. Given three integers , and , we say that if and only if (in this case, we can say that is congruent to modulo ). For example, because . because . This relation has many properties. Let's list the most basic ones first:

3. and

4. , for any integer

Proofs