How do you find the remainder of congruence?

Finding the remainder of a congruence involves simplifying the expression to find a smaller, non-negative integer that is equivalent (congruent) to the original expression modulo a given number. Here's a breakdown of the process:

Understanding Congruence

Two integers, a and b, are congruent modulo n if their difference (a - b) is divisible by n. This is written as:

a ≡ b (mod n)

This means a and b have the same remainder when divided by n.

Methods for Finding Remainders

Several techniques can be used to simplify a congruence and find the remainder:

1. Direct Division: If the numbers are small enough, you can directly divide a by n and find the remainder. This remainder is congruent to a (mod n).

   Example: 17 ≡ 3 (mod 7) because 17 divided by 7 has a remainder of 3.

2. Simplifying with Modular Arithmetic Rules:

   • Addition/Subtraction: If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n) and a - c ≡ b - d (mod n).
   • Multiplication: If a ≡ b (mod n), then ac ≡ bc (mod n).
   • Exponentiation: If a ≡ b (mod n), then a^k ≡ b^k (mod n) for any positive integer k.

3. Reducing Intermediate Values: During calculations (especially with large numbers or exponents), reduce intermediate results modulo n to keep the numbers manageable.

   Example: To find 2¹²⁴ (mod 7), we can observe that 2³ = 8 ≡ 1 (mod 7). Then, we can rewrite 2¹²⁴ as (2³)⁴¹ * 2¹. Therefore:

   2¹²⁴ ≡ (1)⁴¹ * 2 ≡ 2 (mod 7)

   So, the remainder is 2.

4. Using Euler's Theorem or Fermat's Little Theorem:

   • Euler's Theorem: If a and n are coprime (i.e., their greatest common divisor is 1), then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function (the number of integers less than n that are coprime to n).
   • Fermat's Little Theorem: If p is a prime number, then for any integer a not divisible by p, a^p-1 ≡ 1 (mod p). This is a special case of Euler's Theorem.

   Example: Find 3¹² (mod 5). Since 5 is prime, we can use Fermat's Little Theorem: 3⁴ ≡ 1 (mod 5). Then, 3¹² ≡ (3⁴)³ ≡ 1³ ≡ 1 (mod 5). So, the remainder is 1.

Example Walkthrough

Let's find the remainder when 2¹²⁴ is divided by 7.

1. Look for a pattern or smaller power: Calculate the remainders of small powers of 2 modulo 7:

   • 2¹ ≡ 2 (mod 7)
   • 2² ≡ 4 (mod 7)
   • 2³ ≡ 8 ≡ 1 (mod 7)

2. Use the pattern: Since 2³ ≡ 1 (mod 7), we can write 2¹²⁴ as (2³)⁴¹ * 2¹.

3. Simplify: 2¹²⁴ ≡ (1)⁴¹ 2 ≡ 1 2 ≡ 2 (mod 7)

Therefore, the remainder is 2.

Conclusion

Finding the remainder of a congruence often involves simplifying the expression using properties of modular arithmetic and looking for patterns to reduce large numbers to smaller, manageable ones. Euler's theorem and Fermat's Little Theorem can be very powerful tools in specific situations. Ultimately, the goal is to find a number between 0 and n-1 that is congruent to the original expression modulo n.