Congruence

Definition of Congruence

  • Congruence is defined with respect to a positive integer m.
  • Two integers a and b are congruent modulo m if they give the same remainder when divided by m.
  • This relationship is represented as:
  • a ≡ b (mod m)
  • Example:
  • 17 ≡ 11 (mod 6)
  • Both 17 and 11 leave a remainder of 5 when divided by 6.

Alternative Method for Checking Congruences

  • Two statements are equivalent for checking if a and b are congruent modulo m:
  1. a ≡ b (mod m)
  2. a - b is divisible by m.
  • To check for congruence, you can use the divisibility approach.
  • Example:
  • For the congruence 17 ≡ 11 (mod 6):
    • Compute 17 - 11 = 6, which is divisible by 6.

Theorem of Congruences

  • For integers a and b and positive integer m:
  • a ≡ b (mod m)
    is equivalent to
  • a mod m = b mod m
  • Example:
  • 17 ≡ 11 (mod 6) is equivalent to both 17 mod 6 = 5 and 11 mod 6 = 5.

Finding the Modulo

Example 1: 921 mod 12
  • Solution:
  1. 921 ÷ 12 = 76.75
  2. 76 × 12 = 912
  3. 921 - 912 = 9
  4. Thus, 921 ≡ 9 (mod 12)
Example 2: 304 mod 3
  • Solution:
  1. 304 ÷ 3 = 101.33
  2. 101 × 3 = 303
  3. 304 - 303 = 1
  4. Therefore, 304 ≡ 1 (mod 3)
Example 3: 4255 mod 4
  • Solution:
  1. 4255 ÷ 4 = 1063.75
  2. 1063 × 4 = 4252
  3. 4255 - 4252 = 3
  4. Thus, 4255 ≡ 3 (mod 4)
Example 4: 888 mod 8
  • Solution:
  • 888 ÷ 8 = 111, remainder is 0.
  • Therefore, 888 ≡ 0 (mod 8)
Example 5: 555 mod 6
  • Solution:
  1. 555 ÷ 6 = 92.5
  2. (0.5) × 6 = 3
  3. Therefore, 555 ≡ 3 (mod 6)

Least Residues

  • The least residue of a modulo m is the smallest non-negative remainder when a is divided by m.
  • It must satisfy:
  • 0 ≤ r < m
  • The least residue set is {0, 1, 2, …, m-1}.

Applications of Residues

Example 1: Days of the Week
  • What day will it be in 65 days from Monday?
  • 65 ÷ 7 = 9 remainder 2.
  • Thus, 65 ≡ 2 (mod 7) → Count 2 days from Monday → Wednesday.
Example 2: Months of the Year
  • What month was it 26 months ago from December?
  • 26 ÷ 12 = 2 remainder 2.
  • Thus, 26 ≡ 2 (mod 12) → 2 months back from December → October.
Example 3: Time Calculation
  • What time will it be in 100 hours from 8 o'clock?
  • 100 ÷ 12 = 8 remainder 4.
  • Thus, 100 ≡ 4 (mod 12) → Count 4 hours from 8 o'clock → 12 o'clock.
Example 4: Days Calculation
  • What day will it be in 347 days from Saturday?
  • 347 ÷ 7 = 49 remainder 4.
  • Thus, 347 ≡ 4 (mod 7) → Count 4 days from Saturday → Wednesday.
Example 5: Time Calculation
  • What time will it be in 130 hours from 6 o'clock?
  • 130 ÷ 12 = 10 remainder 10.
  • Thus, 130 ≡ 10 (mod 12) → Count 10 hours from 6 o'clock → 4 o'clock.