Skip to main content
LibreTexts - Ukrayinska

3.3: Лінійні конгруенції

Оскільки конгруенції аналогічні рівнянням, природно запитати про розв'язки лінійних рівнянь. У цьому розділі ми будемо обговорювати лінійні конгруенції однієї змінної та їх рішення. Почнемо з визначення лінійних конгруенцій.

Конгруентність виду,axb(mod m) деx знаходиться невідоме ціле число, називається лінійною конгруентністю в одній змінній.

Важливо знати, що якщоx0 це рішення для лінійної конгруентності, то всі цілі числаxi такі, якіxix0(mod m) є розв'язками лінійної конгруентності. Зверніть увагу також,axb(mod m) що еквівалентно лінійному рівнянню діофанту, тобто існуєy таке, щоaxmy=b. Доведено теореми про розв'язки лінійних конгруенцій.

a,bmДозволяти і бути цілі числа такі, щоm>0 і нехайc=(a,m). Якщоc не ділитьсяb, то конгруентність неaxb(mod m) має рішень. Якщоcb, тоaxb(mod m)

має точноc неконгруентні рішення по модулюm.

Як ми вже згадували раніше,axb(mod m) еквівалентнийaxmy=b. За теоремою 19 про діофантові рівняння ми знаємо, що якщоc не ділитиb, то рівняння, неaxmy=b має розв'язків. Зверніть увагу також, що якщоcb, то існує нескінченно багато рішень, змінна якихx задаєтьсяx=x0+(m/c)t

Таким чином, наведені вище значенняx є розв'язками конгруентностіaxb(mod m). Тепер нам належить визначити кількість неконгруентних рішень, які ми маємо. Припустимо, що два рішення є конгруентними, тобтоx0+(m/c)t1x0+(m/c)t2(mod m).
таким чином ми отримуємо(m/c)t1(m/c)t2(mod m).
Тепер помічаємо, що(m,m/c)=m/c іt1t2(mod c).
таким чином ми отримуємо набір неконгруентних рішень, заданихx=x0+(m/c)t, деt приймається по модулюc.

Зверніть увагу, що якщоc=(a,m)=1, то існує унікальне рішення по модулю m для рівнянняaxb(mod m).

Знайдемо всі рішення конгруентності3x12(mod 6). Зверніть увагу, що(3,6)=3 і312. Таким чином, існує три неконгруентних рішення по модулю6. Ми використовуємо алгоритм Евкліда для пошуку розв'язку рівняння,3x6y=12 як описано в главі 2. В результаті отримуємоx0=6. Таким чином, три неконгруентні рішення задаютьсяx1=6(mod 6),x1=6+2=2(mod 6) іx2=6+4=4(mod 6).

Як ми вже згадували раніше в Зауваження 2, конгруентністьaxb(mod m) має унікальне рішення, якщо(a,m)=1. Це дозволить говорити про модульних інверсах.

Розв'язокax1(mod m) для конгруентності для(a,m)=1 називаєтьсяa модульним оберненим модулем mˉa.

Модульна обернена 7 по модулю 48 дорівнює 7. Зверніть увагу, що рішення для7x1(mod 48) єx7(mod 48).

Вправи

  1. Знайти всі рішення3x6(mod 9).
  2. Знайти всі рішення3x2(mod 7).
  3. Знайти обернене по модулю 13 з 2 і 11.
  4. Показати, що якщоˉa є оберненимa модулемm іˉb є оберненим поb модулюm, тоˉaˉb є зворотним поab модулюm.

Дописувачі та атрибуція