Используя алгоритм Евклида найти НОД(1573

Шаг i
di qi=[di-2/ di-1] ai= ai-2- qi∙ ai-1 bi =bi-2- qi∙ bi-1 ai∙1573+bi ∙308=di
-1 1573 - 1 0 1*1573+0*308=1573
0 308 - 0 1 0*1573+1*308=308
1 33 [1573/308]=5 1-5*0=1 0-5*1=-5 1*1573-5*308=33
2 11 [308/33]=9 0-9*1=-9 1-9*(-5)=46 -9*1573+46*308= 11
3 0 [33/11]=3 1-3*(-9)=28 -5-3*46=-143 28*1573-143*308=0
Итак, -9*1573+46*308=11, следовательно, А=-9, В=46, НОД(1573,308)=11
Теорема Ферма и циклотомические классы