Modular Arithmetic

Before we launch into a discussion on solving the Chinese Remainder Theorem, we have to understand how to solve linear congruences. In algebra, a linear equation generally takes the form ax = b, where a and b are real numbers. A linear congruence takes the form

where a, b are given integers and n is a given positive integer. The difference between a linear congruence and an algebraic linear equation is that linear congruences have more than one solution. Theorem: If d = gcd(a, n), then the linear congruence

ax ≡ b (mod n)

has a solution if and only if d divides b. If d does divide b, and if x₀ is any solution, then the general solution is given by

x = x₀ + (nt / d)

where t ∈ Z. Example 1: Let’s consider the congruence. Here a = 10, b = 6 and n = 12, so d = gcd(10, 12) = 2. 2 divides b = 6, so there are two classes of solutions. Taking x₀ = 3 as a particular solution, so the general solution has the form To make this clearer, let’s look at another example with a step-by-step walk-through. Example 2: Consider the congruence, Step 1: Calculate d = gcd(a, n) and see if d divides b. If b doesn’t divide d we stop, otherwise we move to step 2. In this example, d = gcd(10, 14) = 2, which divides 6, so solutions do exist. If x₀ is any solution, then the general solution is Step 2: To find x₀, we divide the original congruence through by gcd(10, 14) = 2 to give Step 3: Since gcd(5, 3) = 1, we note that 3 ≡ 10 (mod 7), with 10 divisible by 5, we replace the congruence with And then divide by 5, which is coprime to 7, to give Thus x₀ = 2 is a solution, so the general solution has the form Chinese Remainder Theorem The Chinese remainder theorem is a system of simultaneous linear congruences. Theorem: Let n₁, n₂,…, n_k be pairwise relatively prime positive integers, with gcd(n_i, n_j) = 1 whenever i ≠ j, and let a₁, a₂,…, a_k be any integers. Then the solutions of the simultaneous congruences

x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂),… x ≡ a_k (mod n_k)

form a single congruence class (mod n), where n = n₁n₂…n_k. Example 1: Solve the system of congruences; Step 1: Find n by multiplying the 3 moduli together as n can be factored into prime powers. n = 5 * 11 * 19 = 1045 Step 2: Simplify each congruence so it is in the form x ≡ b (mod n). We use the extended Euclidian algorithm. 3x ≡ 2 (mod 5) Extended Euclid: 5 = 3(1) + 2 3 = 2(1) + 1 => 1 = 3 – 2 = 3 – (5 – 3) = 3(2) + (-1)5 Since 3 is multiplied by 2, we multiply the whole congruence by 2 to get rid of the 3, leaving x on its own. 2*3x ≡ 2*2 (mod 5) x ≡ 4 (mod 5) x ≡ -1 (mod 5) Repeat for the other 2 congruences. -3*7x ≡ -3*4 (mod 11) x ≡ -12 (mod 11) x ≡ -1 (mod 11) -7*8x ≡ -7*3 (mod 19) x ≡ -21 (mod 19) x ≡ -2 (mod 19) Step 3: Next we want to use the following formula to determine the overall congruence: x ≡ a₁p₂ a₃d₁ + a₂ p₁p₃d₂ + a₃ p₁p₂d₃ (mod n) We already know n = p₁p₂p₃ so p₁ = 5, p₂ = 11 and p₃ = 19. The numbers we have just calculated from the 3 congruences are a₁ = -1, a₂ = -1 and a₃ = (-2). x ≡ (-1)*11*19*d₁ + (-1)*5*19*d₂ + (-2)*5*11*d₃ (mod 1045) All that remains is to calculate the d values. 11*19d₁ ≡ d₁ (mod 5) 209d₁ ≡ -1 (mod 5) d₁ ≡ -1 (mod 5) 5*19d₂ ≡ d₂ (mod 11) 95d₂ ≡ 7 (mod 11) d₂ ≡ 7 (mod 11) 5*11d₃ ≡ d₃ (mod 19) 55d₃ ≡ -2 (mod 19) d₃ ≡ -2 (mod 19) Step 4: Substitute the d values into the equation and simplify. x ≡ (-1)*11*19*(-1) + (-1)*5*19*7 + (-2)*5*11*(-2) (mod 1045) x ≡ 209 - 665 + 220 (mod 1045) x ≡ -236 (mod 1045) x ≡ 809 (mod 1045) Written by JaneW