Question

Здравствуйте у меня вопрос по математике, мне нужно найти НОД чисел (236, 113) и его линейное представление. НОД я нашел (1), а вот линейное представление найти не знаю как. У меня есть пример выполнения по алгоритму Евклида, но я не пойму от куда взялась цифра 25 во второй строке на втором листочке? и как вообще в том месте произошли вычисления?

Answer 1

Добрый вечер!

Чтобы найти НОД ( наибольший общий делитель ) для чисел 236 и 113 , можно воспользоваться алгоритмом Евклида. Этот алгоритм основан на простой идее: мы делим большее число на меньшее, затем делим получившийся остаток на делитель и так далее, пока не получим остаток равный нулю.

1. Делим 236 на 113:236+113= 2 ост.10

2. Теперь делим 113 на 10:113+10=11 ост.3

3. Затем делим 10 на 3:10+3=3 ост.1

4. И, наконец, делим 3 на 1:3+1= 3 ост.0

Как только получаем остаток равный нулю, останавливаемся. Последнее ненулевое число , в данном случае это 1, будет являться НОД для чисел 236 и 113.

Теперь давайте найдем линейное представление НОД.

Начинаем с конечных значений , которые мы получили на последнем шаге Евклида (3 и 0):

1=3 - 1 * 0

Затем подставляем предыдущие значения (3 и 1 ):

1=3 - 1 * ( 10 - 3 * 3 )= 1 * 10 - 3 * 3 

Теперь подставляем значения , которыми мы делили в процессе алгоритма ( 10 и 3 ) :

1 = ( 113 -10 * 11 ) * 10 - 3 * 3 = 113 * 10 - 11 * 10 * 10 - 3 * 3

 И , наконец, заменяем значения чисел, которые мы делили , исходными числами( 113 и 236 ):

1 = 113 * 10 - 11 * 10 *10 - 3 * ( 236 - 113 * 2 ) = 113 * 10 - 11 * 10 * 10 - 3 * 236 + 3 * 113 * 2

Теперь приводим подобные слагаемые :

1 = ( 10 - 6 ) * 113 + 10 * 10 * 11 - 3 * 236 =

10 * 113 - 6 * 113 + 10 * 10 * 11 - 3 * 236 =

10 * 113 - 6 * 113 + 110 * 11 - 3 * 236 =

10 * 113 - 6 * 113 + 110 * 11 - 3 * 236

Таким образом , НОД для чисел 236 и 113 равен 1 , а линейное представление НОД выглядит так:

1 = 10 * 113 - 6 * 113 + 110 * 11 - 3 * 236