Exercise 1.5

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Find $m$ and $n$ for the pairs $a$ and $b$ given in Ex 1.3

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof}
From exercises 1.3,  1.4, we know that the sequences $(r_i),(m_i),(n_i)$ are given by
\begin{align*}
r_0 &= a ,r_1 = b\
m_0 &= 1, m_1 = 0\
n_0 &= 0,n_1 = 1\
\end{align*}
and for all $i <k$, 
\begin{align*}
r_{i+2}&= r_{i} -q_{i+1} r_{i+1}\
m_{i+2}&= m_{i} -q_{i+1} m_{i+1}\
n_{i+2}&= n_{i} -q_{i+1} n_{i+1}\
\end{align*}
and for all $i$ 
$$r_{i} = m_i a +n_i b.$$
This gives the direct instructions in Python :
\begin{verbatim}
>>> a,b = 187, 221
>>> r0,r1,m0,m1,n0,n1 = a,b,1,0,0,1  
>>> q = r0//r1; 
>>> q = r0//r1; r0,r1,m0,m1,n0,n1 = r1, r0 -q*r1,m1, m0 -q*m1, n1, n0 - q*n1
>>> print(r0,r1,m0,m1,n0,n1)
221 187 0 1 1 0
>>> q = r0//r1; r0,r1,m0,m1,n0,n1 = r1, r0 -q*r1,m1, m0 -q*m1, n1, n0 - q*n1
>>> print(r0,r1,m0,m1,n0,n1)
187 34 1 -1 0 1
>>> q = r0//r1; r0,r1,m0,m1,n0,n1 = r1, r0 -q*r1,m1, m0 -q*m1, n1, n0 - q*n1
>>> print(r0,r1,m0,m1,n0,n1)
34 17 -1 6 1 -5
>>> q = r0//r1; r0,r1,m0,m1,n0,n1 = r1, r0 -q*r1,m1, m0 -q*m1, n1, n0 - q*n1
>>> print(r0,r1,m0,m1,n0,n1)
17 0 6 -13 -5 11
\end{verbatim}
So
 $$17 = 187 \wedge 221 = 6 	imes 187 - 5 	imes 221.$$
Similarly
$$ 17 = 6188 \wedge 4709 = 121 	imes 6188 - 159 	imes 4709.$$
$$1 = 314 \wedge 159 = -40 	imes 314 + 79 	imes159.$$

We obtain the same results with the following Python script :
\begin{verbatim}
def bezout(a,b):
    """input  : entiers a,b
        output : tuple (x,y,d),
        (x,y) solution de ax+by = d, d = pgcd(a,b)
    """
    (r0,r1)=(a,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)
    return (u0,v0,r0)
\end{verbatim}
\end{proof}

Exercise 1.5

Answers

Comments

Exercise 1.5

Answers

Comments

Add answer