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

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

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

$a\cdot x\equiv b(\mathrm{mod}n).$

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

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

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

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

$2\cdot x\equiv 3(\mathrm{mod}4)$

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

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

$4\cdot x\equiv 6(\mathrm{mod}22)$

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

$x=7,x=18.$

Приклади

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

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

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

Приклади

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

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

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

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

Приклади

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

Розв'яжіть систему: $\{\begin{array}{c}7x-3y=5\\ 8x+5y=11\end{array}(\text{mod}23)$ Шаблон:Hider

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

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

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