Розв'язник вправ по дискретній математиці/Кодування/Діофантові рівняння
Розв'язник вправ по дискретній математиці. Кодування. Діофантові рівняння
ред.Приклади
ред.- За допомогою алгоритму Евкліда знайти НСД(12506,12012).
- Є два способи знаходження алгоритму Евкліда. Розглянемо перший з них.
Число 12506 можна записати наступним способом: 1•2•13•13•37; Число 12012 можна записати як:1•2•2•3•7•11•13. Не важко помітити, що в обох прикладах зустрічаються одинакові числа 2 і 13. Перемножаючи ці числа, отримаємо:2•13=26. Число 26 і є НСД (12506,12012)
- Другий спосіб.
Спочатку нам потрібно знайти різницю цих чисел:12506-12012=494. Утворилася нова пара чисел (12012,494). Далі нам потрібно розписати найбільше число з цієї пари,так, щоб воно містило в собі найменше число пари, тобто: 12012=494•24+156. Тепер необхідно створити нову пару чисел. Беремо найменше число з першої пари, а потім число, яке ми додали, коли розкладали найбільше число першої пари,а саме :(494,156). Далі проводжуємо операцію:494=156•3+26. Утворилася ще одна пара чисел (156,26). Продовжуємо:156=26•6+0. Нова пара чисел = (26,0). Оскільки ми не можемо більше розкладати, бо отримаємо в кінці 0, то НСД початкової пари чисел = 26.
- Розв'язати рівняння
- 1) ,
Щоб розв'язати дане діафантове рівняння, достатньо згадати одну характеристику, а саме: Візьмемо рівняння виду ax+by=c. Це рівнянна має корені тоді, коли НСД(a,b) націло ділиться на с. НСД(a,b) цього рівняння=2. А число 7 не ділиться на 2, тому дане рівняння не має коренів.
- 2) ,
Це рівняння має корені адже НСД(2,4) а 32 ділиться на нього. Знайдемо перші корені. За допомогою простої математики ми бачимо, що х=8, у=4. Підставляємо дані корені в наше рівняння: Звідси виражаємо: . Нехай . Тоді . , Отже, корені цього рівняння матимуть вид : , , K Є Z
- 3) ,
Це рівняння має корені. Можна покласти значення у=0, тоді . . Підставляємо корені. ; Нехай Тоді . Маємо корені даного рівняння , , ,K Є Z.
- 4) ,
Це рівняння має корені. Перші корені діафантового рівняння: . Підставляємо корені. . . ; Підставляємо: ; ; Маємо корені даного рівнянна: , K Є Z
- 5) .
Рівняння має корені.Можна скоротити дане рівняння на 2. Маємо: . x=3,y=3. Підставляємо перші відомі корені. . Виражаємо: . Нехай Тоді ; . . Отже, корені рівняння будуть мати вид: , , k Є Z
- Чи є розв'язок і якщо є, то який?
а) , б) .
a)Дане діафантове рівняння не має коренів, бо НСД (15,21,24)=3. А число 16 не ділиться на 3. Тому корені не існують.
б)Корені існують. Покладемо значення z=0 і розділимо на 3. Тоді рівняння буде мати вид: .Знайдемо перші корені :x=7,y=0. Підставимо корені у рівняння: .Виразимо: . Нехай x-7=8k. x=8k+7. Тоді y=-5k. Отже, корені даного рівняння будуть мати вид: , , , K Є Z.