contestada

PLEASE HELP!

Use the Euclidean algorithm to find integers $x$ and $y$ such that $164x + 37y = 1,$ with the smallest possible positive value of $x$. State your answer as a list with $x$ first and $y$ second, separated by a comma.

Respuesta :

abiolataiwo2015

Using the Euclidean algorithm  integer integers $x$ and $y$  is: [ (-30 + 37k ), (133 - 164k) ].  

Euclidean Algorithm

Given:

$164x + 37y = 1

First step

Sequence of quotients

4(37) + 16=164

2(16) + 5=37

3(5) + 1=16

4(1) + 1=5

1(1) + 0=1

       4     2     3     4     1

1 0     1     2     7    30    37

0 1     4     9    31  133  164

Determinant

(164×30) - (37×133)

=4,920-4,921

= -1

164(-30) + 37(133)

=-4,920+4,921

= 1  

Second step

Integer

[(x + bk), (y - ak) ]

Where:

x = -30

y = 133

k=integer

Hence:

[ (-30 + 37k ), (133 - 164k) ]  

Therefore using the Euclidean algorithm the integer is: [ (-30 + 37k ), (133 - 164k) ].  

Learn more about Eucledian Algorithm here:https://brainly.com/question/24836675

#SPJ1

Otras preguntas