Exercise 2.4.1 (Truncated products)

Question

Verify that bx + cy = 1 where $b,c,x,y$ are numbers given in Example 3 in section 1.2. Use no number of more than $10$ digits.

Richard Ganaye · Accepted Answer

\begin{proof} We recall example 3.

{\bf Example 3.} Find $g = (b,c)$ where $b = 5033464705$ and $c = 3137640337$ and determine $x, y$ such that $bx + cy = g$.

\bigskip
The calculations p. 15 give $g = 1$, and
$$x = 107535067, \qquad y = -172509882.$$
So we must verify
$$g = 5033464705 	imes 107535067 - 3137640337 	imes172509882 = 1.$$
We note that
\begin{align*}
 5033464705 	imes 107535067 &\equiv 4294310235 \pmod {10^{10}},\
 3137640337 	imes 172509882 & \equiv 4294310234 \pmod{10^{10}}.
\end{align*}
Therefore $g \equiv 1 \pmod {10^{10}}.$ Since $g = b \wedge c \leq \min(b,c) <10^{10}$, this gives
$$g = 1.$$ 
\end{proof}

Exercise 2.4.1 (Truncated products)

Answers

Comments

Exercise 2.4.1 (Truncated products)

Answers

Comments

Add answer