Skip to main content
LibreTexts - Ukrayinska

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

  1. Last updated
  2. Save as PDF
  • Page ID
    64671

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

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

    Конгруентність виду,\(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\).

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