Application of elementary operations in Euclidean algorithm

by fungarwai, Sep 15, 2018, 11:49 AM

Generating Bézout's identity by elementary operations

$\begin{pmatrix} -1 & a & b\end{pmatrix}
\begin{pmatrix} a & b\\1 & 0\\0 & 1\end{pmatrix}
=\begin{pmatrix} 0 & 0\end{pmatrix}$

After several elementary column operations, $\begin{pmatrix} a & b\\1 & 0\\0 & 1\end{pmatrix}\rightarrow
\begin{pmatrix} d & r\\x & p\\y & q\end{pmatrix}$ which implies

$\begin{pmatrix} -1 & a & b\end{pmatrix}
\begin{pmatrix} d & r\\x & p\\y & q\end{pmatrix}
=\begin{pmatrix} 0 & 0\end{pmatrix}$

The Bézout's identity for a,b is $ax+by=d$

Example

Application in Chinese remainder theorem

$x\equiv a\pmod{3},x\equiv b\pmod{5},x\equiv c\pmod{7}$

Consider $\frac{3\times 5\times 7}{3}=35$,$\frac{3\times 5\times 7}{5}=21$,$
\frac{3\times 5\times 7}{7}=15$ which is required by Chinese remainder theorem

$\begin{pmatrix} 35 & 21 & 15\\1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{pmatrix}
\rightarrow
\begin{pmatrix} 5 & 21 & 15\\1 & 0 & 0\\0 & 1 & 0\\-2 & 0 & 1\end{pmatrix}
\rightarrow
\begin{pmatrix} 5 & 1 & 15\\1 & -4 & 0\\0 & 1 & 0\\-2 & 8 & 1\end{pmatrix}$

The Bézout's identity is $-4\times 35+1\times 21+8\times 15=1$

$35^{-1}\equiv -4\equiv 2\pmod{3},21^{-1}\equiv 1\pmod{5},
15^{-1}\equiv 8\equiv 1\pmod{7}$

$x\equiv 2\times 35\times a+1\times 21\times b+1\times 15\times c\pmod{105}$

Comment

0 Comments

Notable algebra methods with proofs and examples

avatar

fungarwai
Shouts
Submit
  • Nice blog!

    by Inconsistent, Mar 18, 2024, 2:41 PM

  • hey, nice blog! really enjoyed the content here and thank you for this contribution to aops. Sure to subscribe! :)

    by thedodecagon, Jan 22, 2022, 1:33 AM

  • thanks for this

    by jasperE3, Dec 3, 2021, 10:01 PM

  • I am working as accountant and studying as ACCA student now.
    I graduated applied mathematics at bachelor degree in Jinan University but I still have no idea to find a specific job with this..

    by fungarwai, Aug 28, 2021, 4:54 AM

  • Awesome algebra blog :)

    by Euler1728, Mar 22, 2021, 5:37 AM

  • I wonder if accountants need that kind of math tho

    by Hamroldt, Jan 14, 2021, 10:55 AM

  • Nice!!!!

    by Delta0001, Dec 12, 2020, 10:20 AM

  • this is very interesting i really appericate it :)

    by vsamc, Oct 29, 2020, 4:42 PM

  • this is god level

    by Hamroldt, Sep 4, 2020, 7:48 AM

  • Super Blog! You are Pr0! :)

    by Functional_equation, Aug 23, 2020, 7:43 AM

  • Great blog!

    by freeman66, May 31, 2020, 5:40 AM

  • cool thx! :D

    by erincutin, May 18, 2020, 4:55 PM

  • How so op???

    by Williamgolly, Apr 30, 2020, 2:42 PM

  • Beautiful

    by Al3jandro0000, Apr 25, 2020, 3:11 AM

  • Nice method :)

    by Feridimo, Jan 23, 2020, 5:05 PM

  • This is nice!

    by mufree, May 26, 2019, 6:40 AM

  • Wow! So much Algebra.

    by AnArtist, Mar 15, 2019, 1:19 PM

  • :omighty: :omighty:

    by AlastorMoody, Feb 9, 2019, 5:17 PM

  • 31415926535897932384626433832795

    by lkarhat, Dec 25, 2018, 11:53 PM

  • rip 0 shouts and 0 comments until now

    by harry1234, Nov 17, 2018, 8:56 PM

20 shouts
Tags
About Owner
  • Posts: 859
  • Joined: Mar 11, 2017
Blog Stats
  • Blog created: Sep 15, 2018
  • Total entries: 18
  • Total visits: 5839
  • Total comments: 8
Search Blog
a