Здравствуйте у меня вопрос по математике, мне нужно найти НОД чисел (236, 113) и его линейное представление. НОД я нашел (1), а вот линейное представление найти не знаю как. У меня есть пример выполнения по алгоритму Евклида, но я не пойму от куда взялась цифра 25 во второй строке на втором листочке? и как вообще в том месте произошли вычисления?
Добрый вечер!
Чтобы найти НОД ( наибольший общий делитель ) для чисел 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
Наши педагоги максимально быстро дадут на него развёрнутый ответ. Это бесплатно!
Задать вопрос
