Розв'язник вправ по дискретній математиці/Кодування/Модульна арифметика

Розв'язання лінійних рівнянь

Лінійне рівняння записується у вигляді

$a\cdot x\equiv b{\pmod {n}}.$

Розв'язання можна отримати безпосередньо діленням $x\equiv {\frac {b}{a}}{\pmod {n}}$ або за допомогою формули

$x\equiv b\cdot a^{\varphi (n)-1}{\pmod {n}},$ якщо НСД $(a,n)=1,$ тобто взаємно прості.

Функція $\varphi (n)$ — функція Ейлера, яка дорівнює кількості натуральних чисел, не більших n і взаємно простих з ним.

Якщо НСД $(a,n)\not =1$, рівняння або має не єдиний розв'язок, або не має розв'язку. Як легко побачити, рівняння

$2\cdot x\equiv 3{\pmod {4}}$

не має розв'язків на множині натуральних чисел.

Інше рівняння

$4\cdot x\equiv 6{\pmod {22}}$

має два розв'язки

$x=7,\;x=18.$

Приклади

• Розв'язати рівняння $3x=2{\pmod {7}}$.

Розв'язання.  

$x={\frac {2}{3}}={\frac {2+7k}{3}}$.

Так як, $0=7=7*k{\pmod {7}}$, тому додавати або віднімати, фактично нуль, можна скільки завгодно разів.

Підбираємо ціле число $k$, так щоб чисельник націло поділився на знаменник. Не складно побачити, що, $k=1$.

Тоді $x={\frac {2}{3}}={\frac {2+7}{3}}={\frac {9}{3}}=3$.

Отже, $x=3$. Виконаємо перевірку: $3*3=9=9-7=2{\pmod {7}}$.

Розв'язання через піднесення в степінь.  

$x={\frac {2}{3}}=2*{\frac {1}{3}}$.

Так, як $a^{\varphi (n)}=1{\pmod {n}}$, то ${\frac {1}{a}}=a^{\varphi (n)-1}{\pmod {n}}$.

Обчислимо ${\frac {1}{3}}=3^{\varphi (7)-1}$. Так як, 7 - просте число, то, згідно з властивостями функції Ейлера $\varphi (7)=7-1=6$.

Отже, ${\frac {1}{3}}=3^{\varphi (7)-1}=3^{5}{\pmod {7}}$.

Так як, $3^{2}{\pmod {7}}=9=2$, то $3^{5}=(3^{2})^{2}*3=2^{2}*3=12=5$.

Звідси ${\frac {1}{3}}=5$. Отже $x={\frac {2}{3}}=2*5=3$.

Отже, $x=3$. Виконаємо перевірку: $3*3=9=9-7=2{\pmod {7}}$.

• Розв'язати рівняння $13x=2{\pmod {53}}$.

Розв'язання.  

$x={\frac {2}{13}}={\frac {2+53k}{13}}$.

Треба підібрати ціле число $k$, так щоб чисельник націло поділився на знаменник.

Для цього спростимо вираз: ${\frac {2+53k}{13}}=\left|53=13*4+1\right|={\frac {2+(13*4+1)k}{13}}={\frac {2+k}{13}}+4k$.

Не складно побачити, що, $k=11$ або $k=-2$.

Тоді, якщо $k=-2$.

$x={\frac {2}{13}}={\frac {2-2}{13}}+4*(-2)=-8=45$.

Отже, $x=45$.

Виконаємо перевірку: $13*45=13*(-8)=-104=-104+53*2=2{\pmod {53}}$.

Якщо $k=11$.

$x={\frac {2}{13}}={\frac {2+11}{13}}+4*11=1+44=45$.

Розв'язання через піднесення в степінь.  

$x={\frac {2}{13}}=2*{\frac {1}{13}}{\pmod {53}}$.

${\frac {1}{13}}=13^{\varphi (53)-1}$.

Так як, 53 - просте число, то, згідно з властивостями функції Ейлера $\varphi (53)=53-1=52$. Отже,

${\frac {1}{13}}=13^{51}{\pmod {53}}$.

Так як, $13^{2}{\pmod {53}}=169-53*3=10$, то $13^{51}=(13^{2})^{25}*13=10^{25}*13$.

Так як, $10^{2}{\pmod {53}}=100-53*2=-6$, то $10^{25}*13=(10^{2})^{12}*10*13=(-6)^{12}*130=6^{12}*24$.

Так як, $6^{3}{\pmod {53}}=216-53*4=4$, то $6^{12}*24=(6^{3})^{4}*24=4^{4}*24=4^{3}*2*2*24=|2*24=48=-5|=64*2*(-5)=11*2*(-5)=55*(-2)=2*(-2)=-4$. Отримали, що ${\frac {1}{13}}=-4$.

Отже $x={\frac {2}{13}}=2*(-4)=-8=45$.

Виконаємо перевірку: $13*45=13*(-8)=-104=-104+53*2=2{\pmod {53}}$.

Розв'язання квадратних рівнянь

Приклади

• Розв'язати рівняння $2x^{2}-5x+3=0{\pmod {11}}$.

Розв'язання.  

Рівняння розв'язується як звичайне квадратне рівняння — за допомогою дискримінанту або теореми Вієта. Обчислимо дискримінант:

$D=b^{2}-4ac=5^{2}-4*3*2=25-12*2=25-(12-11)*2=23=1{\pmod {11}}$

$x_{1,2}={\frac {-b\pm {\sqrt {D}}}{2a}}$

$x_{1,2}={\frac {5\pm {\sqrt {1}}}{2*2}}={\frac {5\pm 1}{4}}$

$x_{1}={\frac {5-1}{4}}=1$

$x_{2}={\frac {5+1}{4}}={\frac {3}{2}}={\frac {3+11}{2}}=7$

Виконаємо перевірку: $2*7^{2}-5*7+3=2*49-35+3=2*5-2+3=11=0{\pmod {11}}$.

• Розв'язати рівняння $3x^{2}-5x+4=0{\pmod {13}}$.

Розв'язання.  

Рівняння розв'язується як звичайне квадратне рівняння — за допомогою дискримінанту або теореми Вієта. Обчислимо дискримінант:

$D=b^{2}-4ac=5^{2}-4*3*4=25-3*16=25-3*3=16=3{\pmod {13}}$

Якщо існує ${\sqrt {3}}{\pmod {13}}$, то це буде ціле число від 0 до 12.

Перевіримо, кожне з цих чисел на предмет того чи буде дорівнювати квадрат числа 3:

$12^{2}=(-1)^{2}=1{\pmod {13}}$ — не підходить

$11^{2}=(-2)^{2}=4$ — не підходить

$10^{2}=(-3)^{2}=9$ — не підходить

$9^{2}=(-4)^{2}=16=3$ — підходить.

Отже, ${\sqrt {3}}{\pmod {13}}=\pm 4=\{4,9\}$.

Обчислимо корені:

$x_{1,2}={\frac {-b\pm {\sqrt {D}}}{2a}}$

$x_{1,2}={\frac {5\pm {\sqrt {3}}}{2*3}}={\frac {5\pm 4}{6}}$

$x_{1}={\frac {5+4}{6}}={\frac {9}{6}}={\frac {3}{2}}={\frac {3+13}{2}}=8$

$x_{2}={\frac {5-4}{6}}={\frac {1+13}{6}}={\frac {14}{6}}={\frac {7}{3}}={\frac {7-13}{3}}={\frac {-6}{3}}=-2=11$

Виконаємо перевірку по теоремі Вієта. Перевіримо рівність для суми коренів:

${\frac {-5}{3}}=-(11+8)?$

$5=3*(11+8)$

$5=3*6$

$5=5$ — вірно.

Для добутку коренів:

${\frac {4}{3}}=11*8?$

${\frac {4}{3}}=(11-13)*(8-13)$

$4=2*5*3$

$4=2*2$ — вірно

• Розв'язати рівняння $3x^{2}-2x+4=0{\pmod {7}}$.
  

Розв'язання.  

Рівняння розв'язується як звичайне квадратне рівняння — за допомогою дискримінанту або теореми Вієта. Обчислимо дискримінант:

$D=b^{2}-4ac=2^{2}-4*3*4=4-3*16=4-48=4-48+7*7=5{\pmod {7}}$

Якщо існує ${\sqrt {5}}{\pmod {7}}$, то це буде ціле число від 0 до 6.
Перевіримо, кожне з цих чисел на предмет того чи буде дорівнювати квадрат числа 5:

$6^{2}=(-1)^{2}=1$ — не підходить

$5^{2}=(-2)^{2}=4$ — не підходить

$4^{2}=(-3)^{2}=16=25{\pmod {7}}$ — не підходить

Очевидно, що жодне число ціле число від 0 до 6 в квадраті не дорівнює 5. Отже, корінь з 5 по модулю 7 не існує.
Таким чином, квадратне рівняння не має розв'язків.

Розв'язання лінійних систем

Приклади

• Розв'яжіть систему: $\left\{{\begin{array}{cc}8x-4y=1\\7x+4y=8\end{array}}\right.\ ({\textrm {mod}}\ 19)$

Розв'яжіть систему: $\left\{{\begin{array}{cc}7x-3y=5\\8x+5y=11\end{array}}\right.\ ({\textrm {mod}}\ 23)$

Розв'язання.  

Рівняння розв'язується як звичайна система

Виконаємо перевірку:

Написати програму

Для заданого невід'ємного цілого числа K, знайти довжину найменшого натурального числа N, такого, що N ділиться на K та N містить лише цифру 1. Програма повертає довжину N. Якщо такого N немає, поверніть -1.

• Приклад. Для K = 1 відповідь 1.
• Приклад. Для K = 2 відповідь -1.
• Приклад. Для K = 3 відповідь 3. Бо, 111 = 3 * 37.
• Приклад. Для K = 7 відповідь 6.