Молодежь и наука 2017

217 Задачи, иллюстрирующие практическое применение цепных дробей и мо- тивирующие на их изучение: 1)решение неопределенных уравнений первой степени с двумя неизвестными с помощью цепных дробей; 2) расчет того, как часто происходят «великие противостояния» между планетами Солнечной сис- темы на примере Земли и Марса. 1. Известно, что решить в целых числах уравнения вида: ax + by = c , где a , b , c ∈ Z (1) например, 3 x + 4 y = 13 можно с помощью сравнений первой степени: ax = c (mod b ). Притом 1) если НОД 1);( = ba , то сравнение имеет единственное решение; 2) если НОД 1 );( >= d ba и c кратно d , то сравнение имеет d решений; 3) если НОД 1 );( >= d ba и c не кратно d , то сравнение 1 не имеет решений. Существует несколько методов решения сравнений: – метод подбора, – на практике для небольших модулей удобно использовать общие свойст- ва сравнений. С их помощью попытаться преобразовать коэффициенты так, чтобы правая часть сравнения делилась на коэффициент при неизвестном x без остатка, то есть будет найдено решение, – с помощью теоремы Эйлера: если 1);( = ba , то ) (mod 1 )( b b a ≡ ϕ . Решение: )4 (mod 13 3 = x ⇒= ,1)13;3( сравнение имеет единственное решение. Мы имеем право прибавлять к любой части сравнения число, кратное мо- дулю, в нашем случае: – 12 к правой части сравнения. )4 (mod 1 3 = x , откуда следует, что 31 = x . Подставим полученное значение в исходное уравнение и найдем 1 4 9 13 1 =− = y . ) (mod 1 b xx = или bt xx + = 1 , где ... ,2 ,1,0 ±±= t подставляя в (1) получим: at y y bt xx − = + = 1 1 , где Z t ∈ . Тогда общим решением уравнения 13 4 3 = + y x является система t y t x 31 43 −= += – ответ. Найдем способ решения неопределенных уравнений первой степени с двумя неизвестными с помощью цепных дробей. Сначала рассмотрим уравнение 1 = + by ax , где НОД 1);( = ba . Представим дробь b a в виде непрерывной дроби:       + = 1 , ,..., 2 ,1 nqnq qq b a .