Introduction to Modular Arithmetic Concepts

Aug 4, 2024

Modular Arithmetic - Part One

Outcomes of the Session

  • Outcome 1: Understand modular arithmetic operation with examples.
  • Outcome 2: Understand the concept of congruence.
  • Outcome 3: Identify valid and invalid congruences.

What is Modular Arithmetic?

  • Definition: A system of arithmetic for integers.
  • Modulus: The value at which numbers wrap around in modular arithmetic (denoted as mod).
  • Example: Clock as an analogy for mod 12.
    • 24-hour day represented by a 12-hour clock.
    • For instance:
      • 15 hours = 3 PM (15 mod 12 = 3)
      • 20 hours = 8 PM (20 mod 12 = 8)
      • 23 hours = 11 PM (23 mod 12 = 11)
  • Cryptography: Central mathematical concept in cryptography using modular arithmetic.

Understanding Congruence

  • Definition: Congruence is represented with a symbol instead of equality, particularly in modular arithmetic.
  • Example:
    • 15 is congruent to 3 mod 12. (15 mod 12 = 3)
    • 23 is congruent to 11 mod 12. (23 mod 12 = 11)

Validity of Congruences

  • General Rule: A is congruent to B mod M means when A is divided by M, the remainder is B.
    • Written as: A = kM + B (where k is any integer)
    • Example: 15 = 12 * 1 + 3; 23 = 12 * 1 + 11.

Why Prefer Congruence Over Equality?

  • Congruence allows flexibility in numbers while maintaining the same remainder.
  • Example: 23 is congruent to 3 mod 10 (as well as 33, 43, etc.)
  • Negative Congruences: -2 can be equivalent to 10 in mod 12.

Valid and Invalid Congruences

  1. Valid:

    • 38 is congruent to 2 mod 12 (38 mod 12 = 2).
    • 38 is congruent to 14 mod 12 (38 mod 12 = 14).
    • 5 is congruent to 0 mod 5 (5 mod 5 = 0).
    • 2 is congruent to -3 mod 5 (2 mod 5 = 2).

  2. Invalid:

    • 10 is congruent to 2 mod 6 (10 mod 6 = 4, not 2).
    • 13 is congruent to 3 mod 13 (13 mod 13 = 0, not 3).

Exercise

  • Check validity for:
    • -8 is congruent to 7 mod 5.
    • -3 is congruent to -8 mod 5.

Conclusion

  • Modular arithmetic is important in various mathematical concepts, especially in cryptography.
  • Understanding congruences helps in identifying valid arithmetic operations under modulus.