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

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

Приклади

• За допомогою алгоритму Евкліда знайти НСД(12506,12012).

• Розв'язати рівняння
• 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$.