"Find y and x such that by + ax = gcd(a,b) in the Gaussian integers"

[ksdhart2]

Hi all. I'm having a big brainfart and I can't seem to grasp what I really think is an easy problem. The full text says:

4) For the following pairs (b, a) find y and x such that by + ax = d where d = GCD(a, b).

b) (b, a) = (18 - 16i, 7 - 2i) in the ring $\displaystyle \mathbb{Z}$

I started by dividing

$\displaystyle \dfrac{18-16i}{7-2i}=\dfrac{158}{53}-\dfrac{76i}{53}$

I then rounded each of these values to the nearest Gaussian integer to get 3 - i

$\displaystyle (3-i)(7-2i)=19-13i \implies 18-16i=(3-i)(7-2i)-(1+3i)$

That gives me the quotient and remainder to "feed" to the next round of division

$\displaystyle \dfrac{7-2i}{-1-3i}=\dfrac{-1}{10}+\dfrac{23i}{10}$

Rounding these values again gives me 0 + 2i

$\displaystyle (0+2i)(-1-3i)=6-2i \implies 7-2i=(0+2i)(-1-3i)+1$

Got another quotient and non-zero remainder, so I go again

$\displaystyle \dfrac{-1-3i}{1}=1(-1-3i)+0$

The remainder is zero, so I stop here. But now I have to build back up, to figure out what x and y are. I tried using the matrix method, but it fell apart:

$\displaystyle \begin{pmatrix}1&1\\ 1&0\end{pmatrix} \cdot \begin{pmatrix}2i&1\\ 1&0\end{pmatrix} \cdot \begin{pmatrix}3-i&1\\ 1&0\end{pmatrix} \cdot \begin{pmatrix}0\\ 1\end{pmatrix} = \begin{pmatrix}1+2i\\ \:2i\end{pmatrix}$

Ought to give me my values for x and y, but it's wrong for some reason.

$\displaystyle (1+2i)(18-16i)+(2i)(7-2i)=54+34i$

Instead of giving me the GCD(18-16i, 7-2i) = 1.

Every step I did matches up nicely with the in-class examples we worked... only the end result is wrong for this problem. The only thing I can maybe think of is that the examples we worked all involved only real numbers. Does this method just not work for complex numbers, or something? Any help or insight would be greatly appreciated.

 

[barrick]

Hi ksdhart2,

I notice that this question has been left unanswered for some time, and I don't know if you are still interested in the answer. Anyway, here it goes.

I'm not quite familiar with your "matrix method". I will start by explaining how I would solve that using another method, and I will come back later to your method, because the first method can help understanding what is wrong with your approach.

Iin this method, the total amount of computation is the same as with matrices, but it has the advantage that you can check each line of the computation. If the final answer is wrong, this allows you to locate the error more easily.

Let $\displaystyle b=18-16i$ and $\displaystyle a=7-2i$. The idea is to write a series of equations:

$\displaystyle \displaystyle\qquad by + ax = z$

and to combine them until we get an equation with $\displaystyle z=\gcd(b,a)$. Note that $\displaystyle \gcd(b,a)$ is defined up to a unit ($\displaystyle \pm1$ or $\displaystyle \pm i$).

We start with the obvious two equations:

\(\displaystyle \displaystyle\qquad\begin{align*}
1\cdot b + 0\cdot a &= 18-16i\\
0\cdot b + 1\cdot a &= 7 - 2i
\end{align*}
\)

Next, we divide $\displaystyle 18-16i$ by $\displaystyle 7 - 2i$; the rounded quotient is $\displaystyle 3-i$. We subtract $\displaystyle 3-i$ times the second equation from the first, giving:

\(\displaystyle \displaystyle\qquad
1\cdot b + (-3 + i)\cdot a = -1 - 3i
\)

You can then repeat the process (the next quotient is $\displaystyle 2i$) until you get an equation with $\displaystyle z = 0$. The next to last equation will have $\displaystyle z = \gcd(b,a)$ and will be your answer.

In fact, it is not necessary to write all the equations in full. You can simply keep a table with all the variables.

\(\displaystyle \displaystyle
\qquad\begin{array}{c|c|c|c}
y & x & z & q\\[2pt]
\hline
1 & 0 & 18 - 16i & \\
0 & 1 & 7 - 2i & 3 - i\\
1 & -3+i & -1 - 3i & 2i\\
-2i & 3+6i & 1 & -1-3i\\
7-2i & -(18-16i) & 0 &
\end{array}
\)

The column labeled $\displaystyle q$ contains the rounded quotient of the last two $\displaystyle z$ values. The next to last row contains the answer:

\(\displaystyle \displaystyle\qquad
(-2i)(18-16i) + (3+6i)(7-2i) = 1
\)

As I mentioned before, if the answer is wrong, you can check each line of the table to locate the error.

As far as your matrix method is concerned, you are apparently building the solution from the bottom up. This means that you should multiply the matrices in the reverse order. Indeed, we have:

\(\displaystyle \displaystyle\qquad
\begin{pmatrix}3-i & 1\\ 1 & 0\end{pmatrix}
\begin{pmatrix}2i & 1\\ 1 & 0\end{pmatrix}
\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}
\begin{pmatrix}0 \\ 1\end{pmatrix}
=\begin{pmatrix}3+6i\\2i\end{pmatrix}
\)

This gives you the solution, except that one sign is wrong. The explanation is in the last line of the table. You are actually rebuilding the solution from a solution of $\displaystyle by - ax = 0$ instead of $\displaystyle by + ax = 0$. You should check your course material for the exact definition of the method.