Найдите линейное разложение НОД чисел а) 607

А)
6 0 7 4 7 7
4 7 7 1 3 0
1 3 0 8 7
8 7 4 3
4 7 7 1
3 9 0 3
  8 7 1
4 5 2
1 3 0
8 7
4 3
1
НОД607, 477=1.
Записываем результаты деления с остатком:
607=1∙477+130⇔130=607-477,
477=3∙130+87⇔87=477-3∙130,
130=1∙87+43⇔43=130-87,
87=2∙43+1⇔1=87-2∙43.
Строим цепочку равенств:
1=87-2∙43=87-2∙130-87=3∙87-2∙130=3∙477-3∙130-2∙130=
=3∙477-11∙130=3∙477-11∙607-477=-11∙607+14∙477.
Итак, НОД607, 477=1=-11∙607+14∙477.
б)
8 9 9 4 9 3
4 9 3 4 0 6
4 0 6 8 7
8 7 5 8
5 8 2 9
4 9 3 1
4 0 6 1
3 4 8 4
5 8 1
5 8 2
4 0 6
8 7
5 8
2 9
0
НОД899, 493=29.
Записываем результаты деления с остатком:
899=1∙493+406⇔406=899-493,
493=1∙406+87⇔87=493-406,
406=4∙87+58⇔58=406-4∙87,
87=1∙58+29⇔29=87-58.
Строим цепочку равенств:
29=87-58=87-406-4∙87=5∙87-406=5∙493-406-406=5∙493-6∙406=
=5∙493-6∙899-493=-6∙899+11∙493.
Итак, НОД899, 493=29=-6∙899+11∙493.
в)
9 6 3 7 1 5
7 1 5 2 4 8
2 4 8 2 1 9
2 1 9 2 9
2 9 1 6
1 6 1 3
1 3 3
7 1 5 1
4 9 6 2
2 1 9 1
2 0 3 7
1 6 1
1 3 1
1 2 4
2 4 8
2 1 9
2 9
1 6
1 3
3
1
НОД963, 715=1.
Записываем результаты деления с остатком:
963=1∙715+248⇔248=963-715,
715=2∙248+219⇔219=715-2∙248,
248=1∙219+29⇔29=248-219,
219=7∙29+16⇔16=219-7∙29,
29=1∙16+13⇔13=29-16,
16=1∙13+3⇔3=16-13,
13=4∙3+1⇔1=13-4∙3.
Строим цепочку равенств:
1=13-4∙3=13-4∙16-13=5∙13-4∙16=5∙29-16-4∙16=5∙29-9∙16=
=5∙29-9∙219-7∙29=68∙29-9∙219=68∙248-219-9∙219=68∙248-77∙219=
=68∙248-77∙715-2∙248=222∙248-77∙715=222∙963-715-77∙715=
=222∙963-299∙715.
Итак, НОД963, 715=1=222∙963-299∙715.