Modular Arithmetic

2 min read

Modular Congruence

Informal Definition: An integer a is considered congruent to an integer b modulo m if a and b have the same remainder when divided by m. Example:

  • 3 is congruent to 5 under modulo 2
    • the mod 2 is not an operation. This is the modulo that we are discussion for our congruence. Formal Definition: Let a and b be integers and m be a positive integer. If m | a-b, then  a is congruent to b modulo m.  
  • We will use the notation , to indicate that  a is congruent to b modulo m
  • Note not the same as

Modular Congruence Theorems

Theorem 1

Extra close brace or missing open brace\text{Let } a,b \in \mathbb{Z}\quad m \in \mathbb{Z}^{+}\\ a \equiv b (\mod m) \iff a \mod m = b \mod m }

Theorem 2

Extra close brace or missing open brace\text{Let } a,b,k \in \mathbb{Z}\quad m \in \mathbb{Z}^{+}\\ a \equiv b (\mod m) \iff a = b + km }

Theorem 3

Extra close brace or missing open brace\text{Let } a,b,c,d \in \mathbb{Z}\quad m \in \mathbb{Z}^{+}\\ a + c \equiv b + d (\mod m)\\ ac \equiv bd (\mod m) }

In modular arithmetic problems, modularly congruent expressions can be interchanged.

Modular Congruence Properties

  • (a+b) mod m = ((a mod m) + (b mod m)) mod m
  • ab mod m = ((a mod m)(b mod m)) mod m

Ex: Find

Ex: (27 + 53) mod 7 27 mod 7 = 6 53 mod 7 = 4 (27 + 53) mod 7 = (6 + 4) mod 7 = 10 mod 7 = 3 or (27 + 53) mod 7 (77 + 3) mod 7 3

Arithmetic Modulo m

  • Define to be the set of nonnegative integers less than m {0,1,…,m-1}
  • We define addition on the integers by by 
    • a b = (a+b) mod m
  • We define multiplication on these integers by  by 
    • a b = (a ⋅ b) mod m

Properties of addition modulo m and multiplication modulo m

Graph View

Backlinks