3.3: Лінійні конгруенції
Оскільки конгруенції аналогічні рівнянням, природно запитати про розв'язки лінійних рівнянь. У цьому розділі ми будемо обговорювати лінійні конгруенції однієї змінної та їх рішення. Почнемо з визначення лінійних конгруенцій.
Конгруентність виду,ax≡b(mod m) деx знаходиться невідоме ціле число, називається лінійною конгруентністю в одній змінній.
Важливо знати, що якщоx0 це рішення для лінійної конгруентності, то всі цілі числаxi такі, якіxi≡x0(mod m) є розв'язками лінійної конгруентності. Зверніть увагу також,ax≡b(mod m) що еквівалентно лінійному рівнянню діофанту, тобто існуєy таке, щоax−my=b. Доведено теореми про розв'язки лінійних конгруенцій.
a,bmДозволяти і бути цілі числа такі, щоm>0 і нехайc=(a,m). Якщоc не ділитьсяb, то конгруентність неax≡b(mod m) має рішень. Якщоc∣b, тоax≡b(mod m)
Як ми вже згадували раніше,ax≡b(mod m) еквівалентнийax−my=b. За теоремою 19 про діофантові рівняння ми знаємо, що якщоc не ділитиb, то рівняння, неax−my=b має розв'язків. Зверніть увагу також, що якщоc∣b, то існує нескінченно багато рішень, змінна якихx задаєтьсяx=x0+(m/c)t
Зверніть увагу, що якщоc=(a,m)=1, то існує унікальне рішення по модулю m для рівнянняax≡b(mod m).
Знайдемо всі рішення конгруентності3x≡12(mod 6). Зверніть увагу, що(3,6)=3 і3∣12. Таким чином, існує три неконгруентних рішення по модулю6. Ми використовуємо алгоритм Евкліда для пошуку розв'язку рівняння,3x−6y=12 як описано в главі 2. В результаті отримуємоx0=6. Таким чином, три неконгруентні рішення задаютьсяx1=6(mod 6),x1=6+2=2(mod 6) іx2=6+4=4(mod 6).
Як ми вже згадували раніше в Зауваження 2, конгруентністьax≡b(mod m) має унікальне рішення, якщо(a,m)=1. Це дозволить говорити про модульних інверсах.
Розв'язокax≡1(mod m) для конгруентності для(a,m)=1 називаєтьсяa модульним оберненим модулем mˉa.
Модульна обернена 7 по модулю 48 дорівнює 7. Зверніть увагу, що рішення для7x≡1(mod 48) єx≡7(mod 48).
Вправи
- Знайти всі рішення3x≡6(mod 9).
- Знайти всі рішення3x≡2(mod 7).
- Знайти обернене по модулю 13 з 2 і 11.
- Показати, що якщоˉa є оберненимa модулемm іˉb є оберненим поb модулюm, тоˉaˉb є зворотним поab модулюm.