Modular arithmetic

Congruence

a ≡ b (mod m)

if

(a - b) mod m is zero

∀a,b ∈ ℤ and m ∈ ℤ⁺

From Discrete mathematics and its applications:

If a and b are integers and m is a positive integer, then a is congruent to b modulo m if m divides a-b.

Then,

• a ≡ b (mod m) is a congruence
• m is its modulus

Eg:

• 17 ≡ 5 (mod 6)
  • ∵ 17-5 = 12, and (12 mod 6) is zero.
• 24 ≢ 14 (mod 6)
  • ∵ 24-14 = 10, and (10 mod 6) is 4 ≠ 0.

Congruence class

Set of all integers which are congruent to a (mod m) constitutes the congruence class of a modulo m.

a (mod m) vs a mod b

a ≡ b (mod m) and a mod m = b are not the same.

• a ≡ b (mod m): a relation on ℤ
• a mod m = b: a function. Arithmetic modulo m.

a mod b is the reminder when a is divided by b.
Like a % b in C.

But there is a link between the two 'mod's:

a ≡ b (mod m)

iff

a mod m = b mod m

where a, b ∈ ℤ and m ∈ ℤ⁺ (a positive integer)

Eg:

19 ≡ 3 (mod 4)

then

19 mod 4  =  3 mod 4
       3  =  3        ✓

Bézout's theorem

aka Bézout's identity

If a, b ∈ ℤ⁺ then ∃s, t ∈ ℤ such that gcd(a, b) = sa + tb

where s and t are known as Bézout's coefficients.

ie, gcd(a, b) can be expressed as a linear combination with integer coefficients for a and b.

Eg:

gcd(6, 14) = 2
(-2 * 6) + (1 * 14) = 2

Solving congruences

Chinese Reminder Theorem

Usable when the moduli of the system of linear congruences are pairwise relatively prime.

From Discrete mathematics and its applications:

When the moduli of a system of linear congruences are pairwise relatively prime, there is a unique solution of the system modulo the product of the moduli.

Eg:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

Biggest one is 7:

 2: ✗ ∵  2(mod 5) is 2 ≠ 3
 9: ✗ ∵  9(mod 2) is 1 ≠ 2
16: ✗ ∵ 16(mod 5) is 1 ≠ 3
23: ✓

—

M = 3 * 5 * 7 = 105

Same solution with Back-substitution method:

Properties

• a ≡ b (mod m) means (a - b) mod m is zero.

• a ≡ b (mod m) means ∃k ∈ ℤ, a = km + b

• a ≡ b (mod m) iff a mod m = b mod m

• If a ≡ b (mod m) and c ≡ d (mod m), then

  • a+c ≡ b+d (mod m)
  • ac ≡ bd (mod m)

• (a+b) mod m = ((a mod m) + (b mod m)) mod m (Note that this is the function mod!)

• (ab) mod m = ((a mod m) * (b mod m)) mod m (Note that this is the function mod!)

• ℤₘ with modular addition constitutes a commutative group (ie, an Abelian group).

Informally speaking,

a⁻¹ ≡ b (mod m) is same as 
0   ≡ (b-a) (mod m)

but a coprime condition is involved??

But, beware: Modular fraction arithmetic is valid only for fractions with denominator coprime to the modulus.

Common notations

• a | b means a divides b. ie, a mod b is zero.
• a +ₘ b = (a + b) mod (m)
• ℤₘ = [0, m) ie, all non-negative integers less than m.

Example usages

DONE 7⁽²⁰¹⁵⁾ % 48 ¹

49         ≡    1  mod 48
7²         ≡    1  mod 48
(7²)¹⁰⁰⁷   ≡    1  mod 48
7.(7²)¹⁰⁰⁷ ≡ (7.1) mod 48
7²⁰¹⁵      ≡    7  mod 48

So the remainder is 7.

TODO Last 2 digits of 17¹⁹⁸ ¹

289 ≡ -11 (mod 100) 17² ≡ -11 (mod 100)

(17²)⁹⁹ ≡ -11 (mod 100)

References

• Chapter 4, Discrete mathematics and its applications (7e) - Kenneth H. Rosen