Question

Solve the problem \(N \equiv 5(\bmod 6) \equiv 4(\bmod 5) \equiv\) \(3(\bmod 4)) \equiv 2(\bmod 3))\) by the Indian procedure and by the Chinese procedure. Compare the methods.

Short answer

In summary, both the Indian procedure and Chinese Remainder Theorem (CRT) procedure can be used to solve systems of simultaneous congruences, giving the same correct solution of \(N=122\). While the Indian procedure is more intuitive, the CRT procedure is more algorithmic and can be more efficient and less error-prone. Therefore, the choice of method depends on the user's preference and familiarity with each procedure.

Step-by-step solution

Understanding the Problem

We are given a system of simultaneous congruences: \begin{align} N &\equiv 5 \pmod{6} \\ N &\equiv 4 \pmod{5} \\ N &\equiv 3 \pmod{4} \\ N &\equiv 2 \pmod{3} \end{align} The goal is to find the smallest non-negative integer \(N\) that satisfies all these congruences.

The Indian Procedure

The Indian procedure is also known as the "step-by-step method." It works by solving the congruences pair by pair. Here's how to do it: 1. Solve the first two congruences to find the smallest \(N_1\) satisfying them. 2. Replace the first two congruences with the new congruence involving \(N_1\). 3. Solve the new first two congruences to find the smallest \(N_2\) satisfying them. 4. Repeat this process until we have found the smallest \(N\) satisfying all the congruences. Solving for \(N_1\): \begin{align} N &\equiv 5 \pmod{6} \\ N &\equiv 4 \pmod{5} \end{align} Multiples of 6 are 6, 12, 18, 24, 30, and so on. Among these, the numbers that leave a remainder of 4 when divided by 5 are 9, 24. So, \(N_1 = 9\) is the smallest number satisfying these congruences. Thus, we have the new system: \begin{align} N &\equiv 9 \pmod{30} \\ N &\equiv 3 \pmod{4} \\ N &\equiv 2 \pmod{3} \end{align} Solving for \(N_2\): \begin{align} N &\equiv 9 \pmod{30} \\ N &\equiv 3 \pmod{4} \end{align} Multiples of 30 are 30, 60, 90, and so on. Among these, the numbers that leave a remainder of 3 when divided by 4 are 63, 123. So, \(N_2 = 63\) is the smallest number satisfying these congruences. Thus, we have the new system: \begin{align} N &\equiv 63 \pmod{120} \\ N &\equiv 2 \pmod{3} \end{align} Solving for \(N_3\): \begin{align} N &\equiv 63 \pmod{120} \\ N &\equiv 2 \pmod{3} \end{align} Multiples of 120 are 120, 240, 360, and so on. Among these, the numbers that leave a remainder of 2 when divided by 3 are 122, 242. So, \(N_3 = 122\) is the smallest number satisfying these congruences. Therefore, the smallest \(N = 122\).

The Chinese Remainder Theorem (CRT) Procedure

The Chinese Remainder Theorem states that for any system of simultaneous congruences with pairwise relatively prime moduli (i.e., gcd(\(M_i\), \(M_j\))=\(1\)), there exists a unique solution modulo the product of the moduli. Here's how to solve it using CRT: 1. Compute the product \(M = M_1 M_2 \cdots M_k\) of all the moduli. 2. For each \(i\), compute \(y_i = M / M_i\) and \(z_i = y_i^{-1} \pmod{M_i}\). 3. Compute the solution \(N\) as \(N \equiv \sum_{i=1}^k a_i y_i z_i \pmod{M}\). Computing the values for our system of congruences: \begin{align} M &= 6 \cdot 5 \cdot 4 \cdot 3 = 360 \\ y_1 &= \frac{360}{6} = 60 \\ y_2 &= \frac{360}{5} = 72 \\ y_3 &= \frac{360}{4} = 90 \\ y_4 &= \frac{360}{3} = 120 \end{align} Computing the \(z_i\) values: \begin{align} z_1 &\equiv 60^{-1} \pmod{6} \implies z_1 = 5 \\ z_2 &\equiv 72^{-1} \pmod{5} \implies z_2 = 3 \\ z_3 &\equiv 90^{-1} \pmod{4} \implies z_3 = 1 \\ z_4 &\equiv 120^{-1} \pmod{3} \implies z_4 = 1 \end{align} Computing the solution: \begin{align} N &\equiv \sum_{i=1}^4 a_i y_i z_i \pmod{360} \\ N &\equiv 5(60)(5) + 4(72)(3) + 3(90)(1) + 2(120)(1) \pmod{360} \\ N &\equiv 1500 + 864 + 270 + 240 \pmod{360} \\ N &\equiv 2874 \pmod{360} \end{align} Which reduces to \(N \equiv 122 \pmod{360}\), so the smallest non-negative solution is \(N=122\).

Comparing Methods

Both methods yield the correct solution, \(N = 122\). The Indian procedure involves solving congruences step by step, which can be more intuitive but may require considerable guesswork and verification of each intermediate step. On the other hand, the Chinese procedure involves a more algorithmic approach and algebraic computations, which can be more efficient and less error-prone. The choice of which method to use depends on the user's preference and familiarity with each procedure.

Key concepts

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after reaching a certain value, called the modulus. Think of it like the hours on a clock—after 12, it wraps back to 1. For instance, with a modulus of 6, numbers reset every 6 units.

In mathematical terms, two numbers are said to be congruent modulo a number if they have the same remainder when divided by that number. For example, 8 and 14 are congruent modulo 6 because both leave a remainder of 2 when divided by 6. This is written as:

• 8 ≡ 14 (mod 6)

Understanding modular arithmetic is essential for solving problems using methods like the Chinese Remainder Theorem or the step-by-step Indian procedure, as these rely on manipulating congruences and finding solutions that satisfy multiple modular conditions.

Congruences

Congruences express the idea of "equivalence" in modular arithmetic. When solving problems involving congruences, we often need to find a number that satisfies several such equivalences simultaneously.

The notation:

• N ≡ a (mod m)

means that N and a have the same remainder when divided by m. For a problem involving multiple congruences like the one we are considering, the task is to find a single a number N that satisfies all given conditions.

The magic of congruences is that they allow complex problems to be broken down into simpler, more manageable parts. Each congruence is a clue leading toward the comprehensive solution.

Number Theory

Number theory is a branch of mathematics focused on the properties and relationships of numbers, particularly integers. This field investigates complex concepts such as divisibility, prime numbers, and modular arithmetic, which are crucial for understanding congruences.

The Chinese Remainder Theorem (CRT) is a classical result in number theory that provides a systematic way to solve systems of simultaneous congruences.

By employing number theory, methods like CRT ensure that solutions to congruence problems are not just found but verified, ensuring mathematical rigor and correctness. It allows mathematicians and students alike to explore solutions that would otherwise seem daunting due to their complexity.

Mathematical Procedures

Mathematical procedures refer to the sequential steps or methods used to solve particular problems. When dealing with modular arithmetic and congruences, two primary procedures stand out: the Indian method and the Chinese Remainder Theorem.

The Indian method involves tackling each congruence separately and systematically until a single solution is found. This step-by-step approach can be intuitive, as it breaks down a larger problem into smaller, digestible parts.

Conversely, the Chinese Remainder Theorem offers a more formalized algorithmic approach. It calculates a solution by considering the product of all moduli and finding appropriate multipliers to piece together the solution using all given congruences. This method is efficient, particularly when dealing with larger systems of congruences.

Both procedures reflect the beauty of mathematics: the ability to use different paths to reach the same destination, each with its advantages and challenges. Understanding these procedures enriches one's problem-solving toolkit and provides deeper insight into the world of number theory.