Problem 3 - A Computational Introduction to Number Theory and Algebra

Question

Let \(a, b \in \mathbb{Z}\) with \(a \geq b \geq 0,\) let \(d:=\operatorname{gcd}(a, b),\) and assume \(d>0\). Suppose that on input \(a, b\), Euclid's algorithm performs \(\lambda\) division steps, and computes the remainder sequence \(\left\\{r_{i}\right\\}_{i=0}^{\lambda+1}\) and the quotient sequence \(\left\\{q_{i}\right\\}_{i=1}^{\lambda}\) (as in Theorem 4.1 ). Now suppose we run Euclid's algorithm on input \(a / d, b / d\). Show that on these inputs, the number of division steps performed is also \(\lambda,\) the remainder sequence is \(\left\\{r_{i} / d\right\\}_{i=0}^{\lambda+1},\) and the quotient sequence is \(\left\\{q_{i}\right\\}_{i=1}^{\lambda} .\)

Step-by-Step Solution

Answer

Answer: The number of steps, remainder sequence, and quotient sequence are the same when Euclid's algorithm is performed on input (a, b) and (a/d, b/d).

Step 1: Euclidean Algorithm for (a, b)

First, apply the Euclidean Algorithm for a pair (a, b): 1. Initially, set \(r_0 = a\) and \(r_1 = b\). 2. If \(r_1 = 0\), then the greatest common divisor is \(r_0\). 3. Otherwise, set \(q_i = \lfloor \frac{r_{i-1}}{r_i} \rfloor\) and \(r_{i+1} = r_{i-1} - q_i \cdot r_i\) for \(i = 1, 2, ..., \lambda\) (until \(r_{\lambda+1} = 0\)).

Step 2: Euclidean Algorithm for (\(\frac{a}{d}\), \(\frac{b}{d}\))

Now apply the Euclidean Algorithm for the pair \((\frac{a}{d}, \frac{b}{d})\): 1. Initially, set \(v_0 = \frac{a}{d}\) and \(v_1 = \frac{b}{d}\). 2. If \(v_1 = 0\), then the greatest common divisor is \(v_0\). 3. Otherwise, set \(p_i = \lfloor \frac{v_{i-1}}{v_i} \rfloor\) and \(v_{i+1} = v_{i-1} - p_i \cdot v_i\) for \(i = 1, 2, ..., \lambda\) (until \(v_{\lambda+1} = 0\)). Now, we show that each step leads to the same remainder and quotient sequences.

Step 3: Number of Division Steps

We need to show that the number of division steps performed is the same \(\lambda\). Since both algorithms start with the same input ratios, the conditions for the next step will be met at the same times in both cases. Hence, the number of steps performed will be the same.

Step 4: Remainder Sequence

Now we show that the following relation holds: \(r_i = d \cdot v_i\) for all \(i = 0, 1, ..., \lambda+1\). We proceed by induction on \(i\). For \(i = 0\) and \(i = 1\), the relation holds as \(r_0 = a = d \cdot v_0\) and \(r_1 = b = d \cdot v_1\). Now assume that \(r_i = d \cdot v_i\) for some arbitrary \(i \geq 1\). In both cases, we compute the remainder \(r_{i+1}\) and \(v_{i+1}\). In the first case, \(r_{i+1} = r_{i-1} - q_i \cdot r_i\) and in the second case, \(v_{i+1} = v_{i-1} - p_i \cdot v_i\). By the induction hypothesis, we can substitute the equalities and get \(d \cdot v_{i+1} = d \cdot v_{i-1} - q_i \cdot d \cdot v_i\). Dividing both sides by \(d\), we get \(v_{i+1} = v_{i-1} - q_i \cdot v_i\). From this, we have the same remainder sequence.

Step 5: Quotient Sequence

Since the quotient sequence is determined by the validation of the floors in each step: \(q_i = \lfloor \frac{r_{i-1}}{r_i} \rfloor\) and \(p_i = \lfloor \frac{v_{i-1}}{v_i} \rfloor\). By comparing the two sequences side by side, if \(r_i = d \cdot v_i\) then we can see that the quotients must be the same as \(\lfloor \frac{d \cdot v_{i-1}}{d \cdot v_i} \rfloor = \lfloor \frac{v_{i-1}}{v_i} \rfloor\). Thus, the quotient sequence is the same for both inputs \((a, b)\) and \((\frac{a}{d}, \frac{b}{d})\). This completes the proof that the number of steps, the remainder sequence, and the quotient sequence are all the same when Euclid's algorithm is performed on input \((a, b)\) and \((a / d, b / d)\).

Key Concepts

Greatest Common Divisor

The greatest common divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. It is a fundamental concept in number theory. For example, for numbers 8 and 12, the GCD is 4, since 4 is the largest number that evenly divides both.

- To find the GCD:

• List out the factors of each number.
• Identify the largest factor that appears in both lists.

However, the Euclidean Algorithm provides a more efficient way to compute the GCD, especially for larger numbers, by repeatedly applying division to get the final result. This method leverages the property that \(\text{gcd}(a, b) = \text{gcd}(b, a \mod b)\).

To find the GCD using the Euclidean Algorithm, you'll repeatedly divide and take remainders until a remainder of zero is reached. The last non-zero remainder is the GCD. In our problem, through this method, we discover that the GCD remains consistent even when processed through division by a common divisor "d", showing uniformity in both quotient and remainder.

Division Steps

In the context of the Euclidean Algorithm, each division step involves dividing two numbers to find both the quotient and the remainder. These steps are crucial because they systematically break down the problem of finding the GCD into smaller increments that ultimately lead to the final answer.

Here is how division steps play out:
- Start with two numbers, say \(a\) and \(b\). Set the larger to be divided by the smaller.- Perform the division \(a = b \cdot q_1 + r_1\), where \(q_1\) is the quotient and \(r_1\) is the remainder.- Replace \(a\) with \(b\), and \(b\) with \(r_1\). Then, repeat the division.- Continue this sequence until the remainder becomes 0.
Each of these steps forms part of a sequence of calculations until the remainder reaches zero. In our problem, when input is scaled by \(d\) (making \(a/d\), \(b/d\)), the number of steps, \(\lambda\), remains the same. This invariance is due to the proportional reduction of both dividends and divisors, thus maintaining the same condition checks and calculations throughout the process.

Remainder Sequence

The remainder sequence is an output of Euclidean Algorithm's division steps. At each stage of division, the remainder is calculated to determine how far off the number is from a complete division. This sequence is significant because it shows the pathway down to the GCD.

When you perform the Euclidean Algorithm on \(a\) and \(b\):

• The division yields remainders \(r_0, r_1, r_2, \ldots, r_{\lambda+1}\) where \(r_{\lambda+1} \text{ is } 0\).
• Each remainder is calculated as \(r_{i+1} = r_{i-1} - q_i \cdot r_i\).

The equation gradually leads us to zero, showcasing the breakdown of division steps.

In the specific problem we explored, if you run the algorithm on \(a/d\) and \(b/d\), the remainder sequence becomes \(r_i / d\) consistent with initial division by \(d\). This means the original sequence divided by \(d\) reflects how the inputs having a common divisor doesn't alter the fundamental relationships between successive remainders, due to their proportionality throughout the division process.