Problem 20 - An Introduction to Mathematical Cryptography

Question

Let \(a, b, m, n\) be integers with \(\operatorname{gcd}(m, n)=1\). Let $$ c \equiv(b-a) \cdot m^{-1} \quad(\bmod n) $$ Prove that \(x=a+c n\) is a solution to $$ x \equiv a \quad(\bmod m) \quad \text { and } \quad x \equiv b \quad(\bmod n) $$ and that every solution to \((2.24)\) has the form \(x=a+c n+y m n\) for some \(y \in \mathbb{Z}\).

Step-by-Step Solution

Answer

The solution is \(x = a + cn\), where every solution has the form \(x = a + cn + ymn\) for \(y \in \mathbb{Z}\).

Step 1: Verify the x ≡ a (mod m) Condition

First, let's express \( x \) as \( x = a + cn \) and verify the condition \( x \equiv a \pmod{m} \). Since \( x = a + cn \), we have: \[ x \equiv a + cn \equiv a \pmod{m} \]Since \( cn \equiv 0 \pmod{m} \) because \( c \equiv (b-a) m^{-1} \pmod{n}\) does not affect the value under modulo \(m\) as the integers \( m \) and \( n \) are coprime. Therefore, \( x \equiv a \pmod{m}.\)

Step 2: Verify the x ≡ b (mod n) Condition

We now need to check that \( x = a + c n \equiv b \pmod{n} \). Substitute \( c \equiv (b-a) m^{-1} \pmod{n} \), where \( m^{-1} \) is the modular inverse of \( m \) modulo \( n \):\[ x = a + c n \equiv a + (b - a)m^{-1}n \equiv b \pmod{n} \] This holds because: \[ a + b - a \equiv b \pmod{n}. \] Thus, \( x \equiv b \pmod{n}.\)

Step 3: Show Every Solution has the Form x = a + cn + ymn

Suppose \( x \equiv a \pmod{m} \) and \( x \equiv b \pmod{n} \). Consider two solutions \( x_1 \equiv x_2 \pmod{m} \) and \( x_1 \equiv x_2 \pmod{n} \). Then \( x_1 - x_2 \equiv 0 \pmod{m} \) and \( x_1 - x_2 \equiv 0 \pmod{n} \), hence:\[ x_1 - x_2 \equiv 0 \pmod{mn}, \]where \( mn \) because \( m \) and \( n \) are coprime. Therefore, the difference \( x_1 - x_2 = ymn \) for some integer \( y \), implying every solution can be written as \( x = a + cn + ymn \).

Key Concepts

modular arithmetic

Modular arithmetic can be thought of as the mathematics of remainders. When you divide two integers, the remainder is the amount left over after dividing. In modular arithmetic, we only focus on these remainders. For instance, when we say "5 modulo 3," we mean the remainder when 5 is divided by 3, which is 2. In this system:

• The number 5 is congruent to 2 modulo 3.
• We write this as: \( 5 \equiv 2 \pmod{3} \).

This concept is crucial because it allows us to simplify complex mathematical problems with cycles or repetitive patterns.
One of its most brilliant applications is in solving congruences, especially using the Chinese Remainder Theorem, which deals with solving simultaneous congruences, just like in the original exercise. Here, understanding that congruences can be thought of in terms of cycles or repeats makes them much easier to manage and solve. Using modular arithmetic simplifies operations on large integers by reducing the problem to operations on smaller integers.

coprime integers

Coprime integers, also known as relatively prime integers, are two numbers that have no common positive integer divisors other than 1. For example, the numbers 9 and 28 are coprime; their greatest common divisor (gcd) is 1. We represent it as:

• \( \text{gcd}(9, 28) = 1 \).

Coprime integers play an essential role in number theory and cryptography.
Their relationship is crucial when dealing with concepts like the Chinese Remainder Theorem, as seen in our exercise where \( \operatorname{gcd}(m, n) = 1 \) indicates that \( m \) and \( n \) are coprime. This property ensures that every solution to our pair of congruences can be uniquely expressed in a more general form without interference from overlapping solutions when both moduli are multiplied together.
Understanding coprime integers helps verify conditions in modular equations and aids in simplifying algebraic expressions when developing solutions.

modular inverse

A modular inverse is similar to how inverse numbers work with multiplication. It is used in this exercise to help solve certain types of congruences. If you have a number \( a \) and a modulus \( m \), the modular inverse of \( a \) is another number \( b \) such that:

• \( a \cdot b \equiv 1 \pmod{m} \).

This means when you multiply \( a \) by its modular inverse \( b \), the product is equivalent to 1 modulo \( m \).
Finding the modular inverse is possible only when \( a \) and \( m \) are coprime. In the original exercise, the modular inverse \( m^{-1} \) helps transform our equation and demonstrate solutions for \( x \). By rewriting equations this way, we can manipulate and solve them more easily. Essentially, the modular inverse allows for division in modular arithmetic, ensuring we find the solution as accurately as possible.