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

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

ред.

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

ред.

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

 

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

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

Функція  функція Ейлера, яка дорівнює кількості натуральних чисел, не більших 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.