Exercise 1.2.3 (Bézout algorithm)

Proof. I give intermediate calculations with arrays similar to the array of page 15.

(a)

$$\begin{array}{cccc}\hfill q_{i+1}\hfill & \hfill r_i\hfill & \hfill x_i\hfill & \hfill y_i\hfill \\ & & & \\ \hfill \hfill & \hfill 423\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 198\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 7\hfill & \hfill 27\hfill & \hfill 1\hfill & \hfill -2\hfill \\ \hfill 3\hfill & \hfill 9\hfill & \hfill -7\hfill & \hfill 15\hfill \end{array}$$

So $(x,y)=(-7,15)$ satisfies $423x+198y=9$

( $-7\times 423+15\times 198=9$).

(b)

$$\begin{array}{cccc}\hfill \hfill & \hfill 71\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 50\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 21\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 2\hfill & \hfill 8\hfill & \hfill -2\hfill & \hfill 3\hfill \\ \hfill 1\hfill & \hfill 5\hfill & \hfill 5\hfill & \hfill -7\hfill \\ \hfill 1\hfill & \hfill 3\hfill & \hfill -7\hfill & \hfill 10\hfill \\ \hfill 1\hfill & \hfill 2\hfill & \hfill 12\hfill & \hfill -17\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill -19\hfill & \hfill 27\hfill \end{array}$$

Since $1=71\times (-19)+50\times 27=1$, we obtain

$$1=71\times (50-19)+50\times (-71+27)=71\times 31-50\times 44,$$

so $(x,y)=(31,44)$ satisfies $71x-50y=1$.

(c)

$$\begin{array}{cccc}\hfill \hfill & \hfill 43\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 64\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 43\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 21\hfill & \hfill -1\hfill & \hfill 1\hfill \\ \hfill 21\hfill & \hfill 1\hfill & \hfill 3\hfill & \hfill -2\hfill \\ \hfill \hfill \end{array}$$

(Note that the first step in Bézout’s algorithm exchanges $a,b$ if $0<a<b$.)

This gives $3\times 43-2\times 64=1$, so $(x,y)=(3,-2)$ satisfies $43x+64y=1$.

(d)

$$\begin{array}{cccc}\hfill \hfill & \hfill 93\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 81\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 6\hfill & \hfill 12\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 1\hfill & \hfill 9\hfill & \hfill -6\hfill & \hfill 7\hfill \\ \hfill 3\hfill & \hfill 3\hfill & \hfill 7\hfill & \hfill -8\hfill \end{array}$$

So $7\times 93-8\times 81=1$: $(x,y)=(7,8)$ is a solution of $93x-81y=3$.

(e)

Since $\gcd (2\times 3,2\times 5,3\times 5)=1$, there is a solution to $6x+10y+15z=1$. To give such a solution of $2(3x+5y)+15z$, definng a new variable $t=3x+5y$, we search first a solution $(t_0,y_0)$ to $$\begin{array}{lll}\hfill 2t+15z=1.& & \hfill \text{(1)}\end{array}$$

If $(x_0,y_0)$ is a solution of

$$\begin{array}{lll}\hfill 3x+5y=t_0,& & \hfill \text{(2)}\end{array}$$

then $(x_0,y_0,z_0)$ is a solution to $6x+10y+15z=1$.

A solution of (1) is $(t_0,z_0)=(-7,1)$, and a solution of $3x+5y=1$ is $(2,-1)$, so $(x_0,y_0)=(-14,7)$ is a solution to $3x+5y=-7$.

This gives $(x_0,y_0,z_0)=(-14,7,1)$ as a solution of $6x+10y+15z=1$.

Note : the preceding arrays are given by the following Python function.

def bezout(a,b):
    sgn_a = 1 if a >= 0 else -1
    sgn_b = 1 if b >= 0 else -1
    (r0, r1)=(abs(a), abs(b))
    (u0, v0) = (1, 0)
    (u1, v1) = (0, 1)
    while r1 != 0:
        q = r0 // r1
        (r2, u2, v2) = (r0 - q * r1, u0 - q * u1, v0 - q * v1)
        (r0, r1) = (r1, r2)
        (u0, u1) = (u1, u2)
        (v0, v1) = (v1, v2)
    x , y, d  = sgn_a * u0, sgn_b * v0, r0
    if x <= 0: x, y = x + abs(b), y - sgn_b * a
    return x, y, d

To obtain intermediate calculations, add

   print(q,r0,’\t’,u0,’\t’,v0)

in the loop. □