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

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

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

Важливо знати, що якщо$x_0$ це рішення для лінійної конгруентності, то всі цілі числа$x_i$ такі, які$x_i\equiv x_0 (mod \ m)$ є розв'язками лінійної конгруентності. Зверніть увагу також,$ax\equiv b (mod\ m)$ що еквівалентно лінійному рівнянню діофанту, тобто існує$y$ таке, що$ax-my=b$. Доведено теореми про розв'язки лінійних конгруенцій.

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

Як ми вже згадували раніше,$ax\equiv b(mod \ m)$ еквівалентний$ax-my=b$. За теоремою 19 про діофантові рівняння ми знаємо, що якщо$c$ не ділити$b$, то рівняння, не$ax-my=b$ має розв'язків. Зверніть увагу також, що якщо$c\mid b$, то існує нескінченно багато рішень, змінна яких$x$ задається $$x=x_0+(m/c)t$$ Таким чином, наведені вище значення$x$ є розв'язками конгруентності$ax\equiv b(mod \ m)$. Тепер нам належить визначити кількість неконгруентних рішень, які ми маємо. Припустимо, що два рішення є конгруентними, тобто $$x_0+(m/c)t_1\equiv x_0+(m/c)t_2(mod \ m).$$ таким чином ми отримуємо $$(m/c)t_1\equiv (m/c)t_2(mod \ m).$$ Тепер помічаємо, що$(m,m/c)=m/c$ і $$t_1\equiv t_2(mod \ c).$$ таким чином ми отримуємо набір неконгруентних рішень, заданих$x=x_0+(m/c)t$, де$t$ приймається по модулю$c$.

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

Знайдемо всі рішення конгруентності$3x\equiv 12 (mod \ 6)$. Зверніть увагу, що$(3,6)=3$ і$3\mid 12$. Таким чином, існує три неконгруентних рішення по модулю$6$. Ми використовуємо алгоритм Евкліда для пошуку розв'язку рівняння,$3x-6y=12$ як описано в главі 2. В результаті отримуємо$x_0=6$. Таким чином, три неконгруентні рішення задаються$x_1=6(mod \ 6)$,$x_1=6+2=2(mod \ 6)$ і$x_2=6+4=4(mod \ 6)$.

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

Розв'язок$ax\equiv 1 (mod\ m)$ для конгруентності для$(a,m)=1$ називається$a$ модульним оберненим модулем m$\bar{a}$.

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

Вправи

1. Знайти всі рішення$3x\equiv 6(mod \ 9)$.
2. Знайти всі рішення$3x\equiv 2(mod \ 7)$.
3. Знайти обернене по модулю 13 з 2 і 11.
4. Показати, що якщо$\bar{a}$ є оберненим$a$ модулем$m$ і$\bar{b}$ є оберненим по$b$ модулю$m$, то$\bar{a}\bar{b}$ є зворотним по$ab$ модулю$m$.

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

• Template:ContribRaji