Matematika-informatika kafedrasi

6-§ Uzluksiz kasrlardan foydalanish usuli. 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚) taqqoslama berilgan bo`lib, (𝑎, 𝑚) = 1 ∧ 𝑎 > 0 bo`lsin. 𝑚 𝑎 kasrni uzluksiz kasrlarga yoyib, uning munosib kasrlarini 𝑃𝑘 𝑄𝑘 (𝑘 = 1̅̅̅,̅𝑛̅) kabi belgilaymiz, bunda 𝑃𝑛 = 𝑚 ∧ 𝑄𝑛 = 𝑎 bo`ladi, u holda 𝑃𝑛𝑄𝑛−1 − 𝑃𝑛−1𝑄𝑛 = (−1) 𝑛 tenglikni 𝑚𝑄𝑛−1 − 𝑎𝑃𝑛−1 = (−1) 𝑛 ko`rinishda yozish mumkin, yoki 𝑎𝑃𝑛−1 ≡ (−1) 𝑛 + 𝑚𝑄𝑛−1 dan 𝑎𝑃𝑛−1 ≡ (−1) 𝑛−1 (𝑚𝑜𝑑𝑚) (2) (2) ni (−1) 𝑛−1 ∙ 𝑏 ga ko`paytirib, (−1) 𝑛−1 ∙ 𝑏 ∙ 𝑎𝑃𝑛−1 ≡ 𝑏(𝑚𝑜𝑑𝑚) (3) (1) va (3) ni solishtirib 𝑥 ≡ (−1) 𝑛−1𝑏 ∙ 𝑃𝑛−1(𝑚𝑜𝑑𝑚) ni hosil qilamiz. Bu erda 𝑃𝑛−1 son 𝑚 𝑎 kasrning (𝑛 − 1) − munosib kasrning suratidan iborat. (1) taqqoslama yagona yechimga ega bo`lgani uchun (3) yechim (1) ning yagona yechimi bo`ladi. MISOL. 68𝑥 ≡ 164(𝑚𝑜𝑑212) (68,164) = 4, 212/4 17𝑥 ≡ 41(𝑚𝑜𝑑53), (17,53) = 1 𝑃𝑘−1 = 25 𝑛 = 3, 𝑛 − 1 = 2 𝑥0 ≡ (−1) 2 ∙ 25 ∙ 41(𝑚𝑜𝑑53) ≡ 18(𝑚𝑜𝑑53) 𝑥 ≡ 18, 71, 124, 177(𝑚𝑜𝑑212).