Scribd
Upload
7 views1 page

Understanding Modular Arithmetic Concepts

This document discusses modular arithmetic and congruence. Modular arithmetic involves numbers "wrapping around" when reaching a certain modulus value. Congruence is an equivalence relation where numbers have the same remainder when divided by the modulus. The document provides examples of finding least residues using the division algorithm and verifying congruences. It also notes several properties of congruence, such as adding, multiplying, and raising congruences to a power while keeping the same modulus.

Uploaded by

John Aldrin M. Villanueva
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7 views1 page

Understanding Modular Arithmetic Concepts

This document discusses modular arithmetic and congruence. Modular arithmetic involves numbers "wrapping around" when reaching a certain modulus value. Congruence is an equivalence relation where numbers have the same remainder when divided by the modulus. The document provides examples of finding least residues using the division algorithm and verifying congruences. It also notes several properties of congruence, such as adding, multiplying, and raising congruences to a power while keeping the same modulus.

Uploaded by

John Aldrin M. Villanueva
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Modular Arithmetic

Congruence/Congruent
 Is an equivalence relation, if a and b are congruent modulo n, then they have no difference
in modular arithmetic under modulo n. Because of this, in modular n arithmetic we usually
use only n numbers 0, 1, 2, ..., n-1. All the other numbers can be found congruent to one of
the n numbers. ... 12+9 ≡ 21 ≡ 1 mod 5.

Modulus
 Is a system of arithmetic for integers, where numbers "wrap around" when reaching a
certain value—the modulus (plural moduli). The modern approach to modular arithmetic
was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published
in 1801.

Least Residue
 In addition, if m > 0 r is the remainder when the Division Algorithm is used to divide b by
m, then r is called the least residue of b (mod m).

Example 1: Verify if the following are true.

 Since 3| (5 – 2), 2 = 5 (mod 3).


 Since 3| 10 – 1, 1 = 10 (mod 3).

Example 2: Find the least residue of the following.

 The least residue of 11 (mod 8) is 3.


 The least residue of 4 (mod 9) is 4.
 The least residue of 25 (mod 5) is 0.

Properties of Congruence

 Congruence is useful because it can be manipulated like ordinary equations. Congruences


to the same modulus can be added, multiplied, and taken to a fixed positive integral power;
i.e., for any a,b,c,d ∈ Z and m,n ∈ N.

You might also like