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

Имеем сравнение ax≡bmod m, a,m=1.
Решение находим по формуле
x0≡-1n-1Pn-1b mod m
где Pn-1 – числитель предпоследней подходящей дроби для числа m/a, разложенного в непрерывную (цепную) дробь .
27x≡35mod 53
Разложим число 53/27 в непрерывную дробь и найдем числитель предпоследней подходящей дроби:
5327=1+2627=1+127/26=1+11+126=q1+1q2+1q3.
Найдем числители подходящих дробей по рекуррентной формуле
Pi+1=qi+1Pi+Pi-1,
где P0=1, P1=q1, i=1,…,n-1:
i
0 1 2 3
qi
1 1 26
Pi
1 1 2 53
Получим, что n=3, Pn-1=P2=2 и решение сравнения имеет вид:
x0≡-13-1∙2∙35 mod 53=70 mod 53=17 mod 53
Ответ: 17 mod 53.