Question

Solve Problem \(\mathrm{I}, 4\), from the Shushu jiuzhang, which s equivalent to \(N \equiv 0(\bmod 11), N \equiv 0(\bmod 5), N \equiv 4\) \(\bmod 9), N \equiv 6(\bmod 8), N \equiv 0(\bmod 7)\)

Short answer

Based on the Chinese Remainder Theorem and given congruences, the unique solution for N modulo the product of the given primes is calculated as 153230.

Step-by-step solution

Examine the congruences

We are given the following congruences: \(N \equiv 0 \pmod{11}\), \(N \equiv 0 \pmod{5}\), \(N \equiv 4 \pmod{9}\), \(N \equiv 6 \pmod{8}\), and \(N \equiv 0 \pmod{7}\).

Compute LCM of moduli

To find the LCM of the moduli (11, 5, 9, 8, 7), first find their prime factorization: 11 -> prime, 5 -> prime, 9 = 3^2, 8 = 2^3, and 7 -> prime. The LCM is the product of the highest power of each prime factor: LCM = \(11^1 \cdot 5^1 \cdot 3^2 \cdot 2^3 \cdot 7^1 = 27720\).

Apply the Chinese Remainder Theorem

Using the Chinese Remainder Theorem, we will find the unique solution modulo 27720. We start by finding \(M_i\) for each modulus \(m_i\), where \(M_i = \frac{\text{LCM}}{m_i}\): \(M_1 = \frac{27720}{11} = 2520\), \(M_2 = \frac{27720}{5} = 5544\), \(M_3 = \frac{27720}{9} = 3080\), \(M_4 = \frac{27720}{8} = 3465\), and \(M_5 = \frac{27720}{7} = 3960\). Now, compute the inverse of \(M_i \pmod{m_i}\), this is \(M_i^{-1}\): \(M_1^{-1} = 2520^{-1} \pmod{11} = 7\), \(M_2^{-1} = 5544^{-1} \pmod{5} = 4\), \(M_3^{-1} = 3080^{-1} \pmod{9} = 4\), \(M_4^{-1} = 3465^{-1} \pmod{8} = 5\), and \(M_5^{-1} = 3960^{-1} \pmod{7} = 1\).

Find N modulo LCM

Now we compute the sum of the product of each congruence residue, its respective \(M_i\), and its respective \(M_i^{-1}\), and take the result modulo the LCM: \(N = (0 \cdot 2520 \cdot 7 + 0 \cdot 5544 \cdot 4 + 4 \cdot 3080 \cdot 4 + 6 \cdot 3465 \cdot 5 + 0 \cdot 3960 \cdot 1) \pmod{27720}\), \(N = (0 + 0 + 49280 + 103950 + 0) \pmod{27720}\), \(N \equiv 153230 \pmod{27720}\). So, the value of N modulo 27720 is 153230.

Key concepts

Congruences

Congruences are a fundamental concept in number theory, which is the branch of mathematics that deals with properties and relationships of numbers, especially the integers. Congruences provide a way to express that two numbers divide by another number, called the modulus, and leave the same remainder.

For example, when we say that two numbers, such as \(A\) and \(B\), are congruent modulo \(n\), formally written as \(A \equiv B \pmod{n}\), it means that when both \(A\) and \(B\) are divided by \(n\), they leave the same remainder. In the context of the exercise given above, for instance, \(N \equiv 4 \pmod{9}\) indicates that the number \(N\), when divided by \(9\), leaves a remainder of \(4\).

An important property is that congruences can be added, subtracted, and multiplied, much like equations. This property is utilized in the Chinese Remainder Theorem to find solutions to systems of linear congruences, the very theorem used to solve the set of congruences presented in the problem above.

Least Common Multiple (LCM)

Least Common Multiple, or LCM, is a concept that refers to the smallest non-negative integer that is a multiple of two or more given numbers. The LCM is a key part in solving systems of congruences, particularly when applying the Chinese Remainder Theorem, as seen in the exercise.

To compute the LCM of multiple numbers, one approach is to perform prime factorization of each number, and then take each prime factor raised to the highest power that appears in any of the factorizations. For instance, the LCM of the moduli in our problem was calculated by finding the highest powers of the prime factors: \(11^1 \cdot 5^1 \cdot 3^2 \cdot 2^3 \cdot 7^1 = 27720\).

Finding the LCM is crucial, as it sets the stage for the subsequent steps in the solution process, determining the periodicity of the combined system of congruences.

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers 'wrap around' after they reach a certain value—the modulus. Imagine a clock with a fixed number of positions; when we go past the last number, we start again at the beginning.

In modular arithmetic, rather than saying that one number is equal to another, we say that they are equivalent or congruent to one another modulo a certain number. The most common use of modular arithmetic is in timekeeping (12 hours post-midnight is the same as 0 hours in a 12-hour clock system). In solving the exercise, modular arithmetic principles were used to calculate inverses of \(M_i\) modulo \(m_i\) and to determine the final value of \(N\) modulo the LCM.

Number Theory

Number theory is often described as the queen of mathematics because of its foundational role in the discipline. It primarily concerns itself with the properties and relationships of numbers, particularly the integers.

Number theory topics are not only fundamental in understanding the deeper workings of numbers but have also found practical applications in areas such as cryptography, computer science, and communications. The problem provided, based on classic Chinese mathematics, is a perfect example of number theory in action, where the application of its principles, such as the Chinese Remainder Theorem, allows us to find specific numbers that meet a set of conditions, or congruences, defined by remainders upon division by certain moduli.