Problem 9 - Algebra: Pure and Applied

Question

Find a greatest common divisor \(d\) of \(a\) and \(b\) in the indicated Euclidean domain, and express \(d=u a+v b\). $$ a=-3+7 \sqrt{3} \quad b=7-\sqrt{3} \quad \text { in } \mathbb{Z}[\sqrt{3}] $$

Step-by-Step Solution

Answer

Perform the Euclidean algorithm reducing norms to find gcd \( d \) and use linear combination steps to express \( d = ua + vb \) in \( \mathbb{Z}[\sqrt{3}] \).

Step 1: Understand the Domain

In the Euclidean domain \( \mathbb{Z}[\sqrt{3}] \), elements are of the form \( a+b\sqrt{3} \) where \( a, b \) are integers. The norm \( N(z) \) of an element \( z = a+b\sqrt{3} \) is defined as \( N(z) = a^2 - 3b^2 \). Norm plays a crucial role in the Euclidean algorithm in \( \mathbb{Z}[\sqrt{3}] \).

Step 2: Calculate Norms of \(a\) and \(b\)

Find the norm of \( a = -3 + 7\sqrt{3} \). \[ N(a) = (-3)^2 - 3(7)^2 = 9 - 147 = -138 \]. Calculating the norm of \( b = 7 - \sqrt{3} \), we get \[ N(b) = 7^2 - 3(-1)^2 = 49 - 3 = 46 \].

Step 3: Apply the Euclidean Algorithm

Perform the division of \( a \) by \( b \) in order to write \( a = q \times b + r \) where the norm of \( r \) is smaller than the norm of \( b \). Compute \( q = \frac{-3+7\sqrt{3}}{7-\sqrt{3}} = \frac{(-3+7\sqrt{3})(7+\sqrt{3})}{N(b)} \) which simplifies with integer components. The remainder \( r = a - qb \) should be calculated accurately to continue the algorithm.

Step 4: Continue until Remainder is Zero

Repeat the division process with \( b \) and \( r \) until the remainder \( r \) becomes zero. When \( r = 0 \), the last non-zero remainder is the greatest common divisor \( d \).

Step 5: Express \(d\) as a Linear Combination

While performing the Euclidean algorithm steps, the coefficients \( u \) and \( v \) for the linear combination can be traced back using the process of backward substitution. Keep track of each step to express \( d = ua + vb \).

Key Concepts

Greatest Common Divisor

The greatest common divisor (GCD) of two numbers is the largest number that divides both of them without leaving a remainder. This concept extends beyond simple integers and can apply to more complex elements, like those in the Euclidean domain \( \mathbb{Z}[\sqrt{3}] \). Here, every element is expressed in the form \( a + b\sqrt{3} \), where \( a \) and \( b \) are integers.
In the exercise, you are asked to find the GCD of the elements \( a = -3 + 7\sqrt{3} \) and \( b = 7 - \sqrt{3} \). The GCD will be a linear combination of \( a \) and \( b \), which means expressing the GCD in the form \( ua + vb \), where \( u \) and \( v \) are also elements of \( \mathbb{Z}[\sqrt{3}] \).
Finding the GCD in domains like this often involves using an associated algorithm, such as the Euclidean algorithm, which simplifies the process.

Euclidean Algorithm

The Euclidean algorithm is a systematic method for finding the greatest common divisor of two elements. It's not only applicable to integers but can also be used in Euclidean domains like \( \mathbb{Z}[\sqrt{3}] \). To understand how it works in such a domain, it's essential to grasp the role of the norm.

• First, we calculate norms of the elements, \( N(a) \) and \( N(b) \), which helps to manage the division in the algorithm.
• The algorithm involves dividing the first element \( a \) by the second element \( b \) and obtaining a quotient \( q \) and remainder \( r \). The condition \( N(r) < N(b) \) must hold true.
• Continue the process by dividing \( b \) by \( r \), repeating until the remainder becomes zero. The last non-zero remainder is the GCD.

This algorithm helps ensure an efficient calculation of the GCD, reducing the size of the problem bit by bit.

Linear Combination

A linear combination in mathematics refers to an expression constructed from a set of terms using scalar multiplication and addition. In the context of finding the GCD, once it is known, you often express it as such a combination.
In this exercise, by executing the Euclidean algorithm, you find coefficients \( u \) and \( v \) such that the GCD can be represented as \( d = ua + vb \). These coefficients \( u \) and \( v \) should be elements of the Euclidean domain, meaning they themselves can be expressed in the form \( m + n\sqrt{3} \), where \( m \) and \( n \) are integers.
Backtracking through the Euclidean algorithm allows you to pinpoint how each remainder is formed, stepping back through prior computations to express the GCD in this linear combination format.

Norm in Algebra

Norms are essential in algebra, especially within specific Euclidean domains. A norm \( N(z) \), associated with an element \( z = a + b\sqrt{3} \) in \( \mathbb{Z}[\sqrt{3}] \), is defined as \( N(z) = a^2 - 3b^2 \).
This function is crucial as it helps determine order and magnitude within the domain, showing how elements compare in size. In calculations, especially when using the Euclidean algorithm:

• It helps to verify the division process, ensuring that reductions occur correctly.
• Norms guide us in confirming the remainder's norm is consistently less than the divisor's norm in iterative divisions.
• The Euclidean algorithm proceeds efficiently because lowering the norm leads directly to the problem's simplification.

Understanding the norm in this context ensures clarity in manipulating and simplifying expressions, making it a vital tool in algebraic calculations.