Problem 11 - An Introduction to Mathematical Cryptography

Question

Let \(a\) and \(b\) be positive integers. (a) Suppose that there are integers \(u\) and \(v\) satisfying \(a u+b v=1\). Prove that \(\operatorname{gcd}(a, b)=1\). (b) Suppose that there are integers \(u\) and \(v\) satisfying \(a u+b v=6\). Is it necessarily true that \(\operatorname{gcd}(a, b)=6 ?\) If not, give a specific counterexample, and describe in general all of the possible values of \(\operatorname{gcd}(a, b)\) ? (c) Suppose that \(\left(u_{1}, v_{1}\right)\) and \(\left(u_{2}, v_{2}\right)\) are two solutions in integers to the equation \(a u+b v=1\). Prove that \(a\) divides \(v_{2}-v_{1}\) and that \(b\) divides \(u_{2}-u_{1}\). (d) More generally, let \(g=\operatorname{gcd}(a, b)\) and let \(\left(u_{0}, v_{0}\right)\) be a solution in integers to \(a u+b v=g\). Prove that every other solution has the form \(u=u_{0}+k b / g\) and \(v=v_{0}-k a / g\) for some integer \(k\). (This is the second part of Theorem 1.11.)

Step-by-Step Solution

Answer

(a) Yes, gcd(a, b) = 1. (b) No, counterexample: a = 2, b = 4. (c) a divides v_2 - v_1; b divides u_2 - u_1. (d) All solutions are u = u_0 + k(b/g), v = v_0 - k(a/g).

Step 1: (a) Determine gcd(a,b) given a linear combination equals 1

To prove that \(\operatorname{gcd}(a, b) = 1\), we start from the given equation \(a u + b v = 1\). The right-hand side being 1 indicates that 1 is a linear combination of \(a\) and \(b\). By Bezout's Lemma, if there exists a linear combination of \(a\) and \(b\) that equals a given number, that number must be a multiple of the greatest common divisor of \(a\) and \(b\). Therefore, the greatest common divisor \(\operatorname{gcd}(a, b)\) must be 1.

Step 2: (b) Evaluate decision for gcd(a,b) when a linear combination equals 6

The existence of integers \(u, v\) such that \(a u + b v = 6\) implies that 6 is a multiple of \(\operatorname{gcd}(a, b)\). However, it does not necessarily mean that \(\operatorname{gcd}(a, b) = 6\). Consider \(a = 2\) and \(b = 4\) where \(\operatorname{gcd}(a, b) = 2\). For instance, \(u = 2, v = -1\) is a solution since \(2(2) + 4(-1) = 6\). Thus, the possible values of \(\operatorname{gcd}(a, b)\) are the divisors of 6: 1, 2, 3, and 6.

Step 3: (c) Prove a condition involving differences of solutions

Given two solutions \((u_1, v_1)\) and \((u_2, v_2)\) to the equation \(a u + b v = 1\), subtract these two equations: \(a(u_1 - u_2) + b(v_1 - v_2) = 0\). This implies \(a(u_1 - u_2) = -b(v_1 - v_2)\). Since \(b \mid b(v_1 - v_2)\) and subtracting gives \(a \mid b(v_1 - v_2)\), by \(a\) dividing the expression, \(b\) divides \(u_2 - u_1\) and \(a\) divides \(v_2 - v_1\).

Step 4: (d) Generalize solution form given gcd(a,b)=g

Let \(g = \operatorname{gcd}(a, b)\) and start from solution \((u_0, v_0)\) for \(a u + b v = g\), according to Bezout's identity. Assume \((u, v)\) is another solution, thus \(a(u - u_0) + b(v - v_0) = 0\). This implies \(a(u - u_0) = -b(v - v_0)\). Therefore, \(u - u_0 = k b / g\) and \(v - v_0 = -ka / g\) for some integer \(k\), proving all solutions can be expressed in this form.

Key Concepts

Bezout's Lemma

Bezout's Lemma is a fundamental result in number theory that connects linear combinations and greatest common divisors (gcd). It states that if you have two integers, say \( a \) and \( b \), there exist integers \( u \) and \( v \) such that their linear combination \( au + bv \) is equal to \( d \), where \( d \) is the gcd of \( a \) and \( b \). In simpler terms, Bezout's Lemma tells us that the greatest common divisor of two numbers is the smallest positive integer that can be expressed as their linear combination.

This lemma is crucial because it directly explains why when a linear combination equals one, \( \operatorname{gcd}(a, b) = 1 \). For instance, if \( au + bv = 1 \), since one is a linear combination of \( a \) and \( b \), it implies the gcd must be one. This idea serves as a key stepping stone in understanding how numbers are related through their common divisors and can be used to solve equations known as Diophantine equations.

Greatest Common Divisor

The greatest common divisor (gcd) of two numbers is the largest number that can exactly divide both numbers without leaving a remainder. For example, the gcd of 8 and 12 is 4 because 4 is the largest number that divides both evenly.

Understanding gcds is useful for various mathematical computations, including simplifying fractions and solving equations like those created by linear combinations and Diophantine equations. In relation to linear combinations, the gcd provides a way to identify the smallest integer expressible as a linear combination of two numbers, helping verify solutions to equations like \( au + bv = d \), where \( d \) must be a multiple of gcd. This concept is essential for deducing the divisibility conditions amongst numbers and forms the backbone of many applications in algebra and number theory.

Linear Combinations

A linear combination involves summing multiples of some coefficients with given values. In mathematical terms, for integers \( a, b \) and coefficients \( u, v \), a linear combination is represented as \( au + bv \).

Linear combinations are powerful because they serve as the foundation for solving many equations, especially those involving integers. The Euclidean algorithm for finding gcd works off the principle of linear combinations, progressively simplifying until the smallest linear expression is found. Additionally, from Bezout's Identity, linear combinations help establish whether a certain integer (like gcd) can be expressed using specific integer coefficients. They also form the basis for solutions to transportation issues and design of some modern algorithms.

Diophantine Equations

Diophantine equations are polynomial equations with integer coefficients that are seeking integer solutions. These are fascinating because they extend beyond high school algebra into more complex realms of mathematics, such as number theory and cryptography.

Classical equations like \( au + bv = d \) are prime examples of linear Diophantine equations, where \( d \) represents the solution we want to achieve. Understanding the integers \( a \), \( b \), and \( d \)'s relationship helps determine possible solutions. In solving these, if \( \operatorname{gcd}(a, b) \mid d \), solutions exist. The structure of these solutions often follows patterns and can be generalized based on the equation's properties, such as in the case where solutions like \( u_0 + k \frac{b}{g} \) and \( v_0 - k \frac{a}{g} \) are derived. Diophantine equations have real-world applications, especially in areas needing integer solutions like time scheduling, distributing resources, and network design challenges.