Розв'язник вправ по дискретній математиці/Кодування/Модульна арифметика
Розв'язник вправ по дискретній математиці. Кодування. Модульна арифметика
ред.Розв'язання лінійних рівнянь
ред.Лінійне рівняння записується у вигляді
Розв'язання можна отримати безпосередньо діленням або за допомогою формули
- якщо НСД тобто взаємно прості.
Функція — функція Ейлера, яка дорівнює кількості натуральних чисел, не більших n і взаємно простих з ним.
Якщо НСД , порівняння або має не єдине рішення, або не має рішення. Як легко побачити, порівняння
не має рішення на множині натуральних чисел.
Інше порівняння
має два рішення
Приклади
ред.- Розв'язати рівняння .
.
Так як, , тому додавати або віднімати, фактично нуль, можна скільки завгодно разів.
Підбираємо ціле число , так щоб чисельник націло поділився на знаменник. Не складно побачити, що, .
Тоді .
Отже, . Виконаємо перевірку: .
.
Так, як , то .
Обчислимо . Так як, 7 - просте число, то, згідно з властивостями функції Ейлера .
Отже, .
Так як, , то .
Звідси . Отже .
Отже, . Виконаємо перевірку: .
- Розв'язати рівняння .
.
Треба підібрати ціле число , так щоб чисельник націло поділився на знаменник.
Для цього спростимо вираз: .
Не складно побачити, що, або .
Тоді, якщо .
.
Отже, .
Виконаємо перевірку: .
Якщо .
.
.
.
Так як, 53 - просте число, то, згідно з властивостями функції Ейлера . Отже,
.
Так як, , то .
Так як, , то .
Так як, , то . Отримали, що .
Отже .
Виконаємо перевірку: .
Розв'язання квадратних рівнянь
ред.Приклади
ред.- Розв'язати рівняння .
Рівняння розв'язується як звичайне квадратне рівняння — за допомогою дискримінанту або теореми Вієта. Обчислимо дискримінант:
Виконаємо перевірку: .
- Розв'язати рівняння .
Рівняння розв'язується як звичайне квадратне рівняння — за допомогою дискримінанту або теореми Вієта. Обчислимо дискримінант:
Якщо існує , то це буде ціле число від 0 до 12.
Перевіримо, кожне з цих чисел на предмет того чи буде дорівнювати квадрат числа 3:
- — не підходить
- — не підходить
- — не підходить
- — підходить.
Отже, .
Обчислимо корені:
Виконаємо перевірку по теоремі Вієта. Перевіримо рівність для суми коренів:
- — вірно.
Для добутку коренів:
- — вірно
- Розв'язати рівняння .
Рівняння розв'язується як звичайне квадратне рівняння — за допомогою дискримінанту або теореми Вієта. Обчислимо дискримінант:
Якщо існує , то це буде ціле число від 0 до 6.
Перевіримо, кожне з цих чисел на предмет того чи буде дорівнювати квадрат числа 5:
- — не підходить
- — не підходить
- — не підходить
Очевидно, що жодне число ціле число від 0 до 6 в квадраті не дорівнює 5. Отже, корінь з 5 по модулю 7
не існує.
Таким чином, квадратне рівняння не має розв'язків.
Розв'язання лінійних систем
ред.Приклади
ред.- Розв'яжіть систему:
Розв'яжіть систему:
Рівняння розв'язується як звичайна система
Виконаємо перевірку:
Написати програму
ред.Для заданого невід'ємного цілого числа K, знайти довжину найменшого натурального числа N, такого, що N ділиться на K та N містить лише цифру 1. Програма повертає довжину N. Якщо такого N немає, поверніть -1.
- Приклад. Для K = 1 відповідь 1.
- Приклад. Для K = 2 відповідь -1.
- Приклад. Для K = 3 відповідь 3. Бо, 111 = 3 * 37.
- Приклад. Для K = 7 відповідь 6.