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

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

Приклади

• За допомогою алгоритму Евкліда знайти НСД(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)$2x+4y=7$,

Щоб розв'язати дане діафантове рівняння, достатньо згадати одну характеристику, а саме: Візьмемо рівняння виду ax+by=c. Це рівнянна має корені тоді, коли НСД(a,b) націло ділиться на с. $2x+4y=7$ НСД(a,b) цього рівняння=2. А число 7 не ділиться на 2, тому дане рівняння не має коренів.

• 2)$2x+4y=32$,

Це рівняння має корені адже НСД(2,4) а 32 ділиться на нього. Знайдемо перші корені. За допомогою простої математики ми бачимо, що х=8, у=4. Підставляємо дані корені в наше рівняння: $2(x-8)+4(y-4)=0.$ Звідси виражаємо:$y-4={\frac {-2(x-8)}{4}}$. Нехай $x-8=4k$. Тоді $x=4k+8.$.$y-4=-2k$ , $y=-2k+4.$ Отже, корені цього рівняння матимуть вид : $x=4k+8$, $y=-2k+4$, K Є Z

• 3)$2x+4y+11z=29$,

Це рівняння має корені. Можна покласти значення у=0, тоді $2x+11z=29$. $x=9,z=1$ . Підставляємо корені. $2(x-9)+11(z-1)=0;$ $z-1={\frac {-2(x-9)}{1}}1$; Нехай $x-9=11k.$ $x=11k+9$ Тоді $z-1=-2k.$ $z=-2k+1$. Маємо корені даного рівняння $x=11k+9$,$z=-2k+1$,$y=0k$,K Є Z.

• 4)$-5x+8y=42$,

Це рівняння має корені. Перші корені діафантового рівняння: $x=-10,y=1$. Підставляємо корені.$-5(x+10)=8(y-1)=0$. $y-1={\frac {5(x+10)}{8}}$.$x=8k-10$ ; Підставляємо: $y-1=5k$; $y=5k+1$; Маємо корені даного рівнянна: $x=8k-10,y=5k+1$, K Є Z

• 5)$6x+8y=42$.

Рівняння має корені.Можна скоротити дане рівняння на 2. Маємо: $3x+4y=21$. x=3,y=3. Підставляємо перші відомі корені. $3(x-3)+4(y-3)=0$. Виражаємо: $y-3={\frac {-3x-3}{4}}$. Нехай $x-3=4k.$ Тоді $x=4k+3$; $y-3=-3k$.$y=3k+3$. Отже, корені рівняння будуть мати вид:$x=4k+3$,$y=-3k+3$, k Є Z

• Чи є розв'язок і якщо є, то який?

а) $15x+24y+21z=16$, б) $15x+24y+21z=105$.

Розв'язання.  

a)Дане діафантове рівняння не має коренів, бо НСД (15,21,24)=3. А число 16 не ділиться на 3. Тому корені не існують.

б)Корені існують. Покладемо значення z=0 і розділимо на 3. Тоді рівняння буде мати вид:$5x+8y=35$.Знайдемо перші корені :x=7,y=0. Підставимо корені у рівняння: $5(x-7)+8y=0$.Виразимо:$y={\frac {-5(x-7)}{8}}$. Нехай x-7=8k. x=8k+7. Тоді y=-5k. Отже, корені даного рівняння будуть мати вид: $x=8k+7$,$y=-5k$,$z=0k$, K Є Z.