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

Матеріал з Вікіпідручника

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

Розв'язання лінійних рівнянь[ред.]

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

Розв'язання можна отримати безпосередньо діленням або за допомогою формули

якщо НСД тобто взаємно прості.

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

Якщо НСД , порівняння або має не єдине рішення, або не має рішення. Як легко побачити, порівняння

не має рішення на множині натуральних чисел.

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

має два рішення

Приклади[ред.]

  • Розв'язати рівняння .
  • Розв'язати рівняння .

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

Приклади[ред.]

  • Розв'язати рівняння .
  • Розв'язати рівняння .
  • Розв'язати рівняння .

Розв'язання лінійних систем[ред.]

Приклади[ред.]

  • Розв'яжіть систему:

Розв'яжіть систему:

Написати програму[ред.]

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

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