Решить сравнение 21x≡45 mod 72 c помощью подходящих дробей

Ax≡bmod m, a,m=1
Наибольший общий делитель d=a,m=21,72=3 делит b=45, тогда сравнение ax≡bmod m имеет d=3 решения.
Разделим обе части сравнения и его модуль на d = 3, получим:
7x≡15mod 24
Разложим число 24/7 в непрерывную дробь и найдем числитель предпоследней подходящей дроби:
247=3+37=3+17/3=3+11+43=3+12+13=q1+1q2+1q3.
Найдем числители подходящих дробей по рекуррентной формуле
Pi+1=qi+1Pi+Pi-1,
где P0=1, P1=q1, i=1,…,n-1:
i
0 1 2 3
qi
3 2 3
Pi
1 3 7 24
n=3, Pn-1=P2=7 и решение сравнения имеет вид:
x0≡-1n-1Pn-1b mod m≡-13-1∙7∙15 mod 24≡105 mod24≡9 mod 24
xk=x0+m∙k, k=0,1,…, d-1
xk=9+24∙k, k=0,1,2
x≡9; 33 ; 57 mod 72.
Ответ: x≡9; 33 ; 57 mod 72.