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

== [[Розв'язник вправ по дискретній математиці]]. Кодування. Діофантові рівняння ==
=== Приклади ===
* За допомогою [[:w:алгоритм Евкліда|алгоритму Евкліда]] знайти [[:w:НСД|НСД]](12506,12012).

{{Hider|
  title = Розв'язання. |
  hidden =1 |
  content =
* Є два способи знаходження алгоритму Евкліда. Розглянемо перший з них.
Число 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.
|
  title-style = color: black;  font-weight: bold; text-align: left;| 
  content-style = color: black;  text-align: left; |
}}


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

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

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

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

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

* Чи є розв'язок і якщо є, то який? 
а) <math>15x+24y+21z=16</math>, 
б) <math>15x+24y+21z=105</math>.

{{Hider|
  title = Розв'язання. |
  hidden =1 |
  content =
a)Дане діафантове рівняння не має коренів, бо НСД (15,21,24)=3. А число 16 не ділиться на 3. Тому корені не існують.


б)Корені існують. Покладемо значення z=0 і розділимо на 3. Тоді рівняння буде мати вид:<math>5x+8y=35</math>.Знайдемо перші корені :x=7,y=0. Підставимо корені у рівняння: <math>5(x-7)+8y=0</math>.Виразимо:<math>y=\frac{-5(x-7)}8 </math>. Нехай x-7=8k. x=8k+7. Тоді y=-5k. Отже, корені даного рівняння будуть мати вид: <math>x=8k+7</math>,<math>y=-5k</math>,<math>z=0k</math>, K Є Z.
|
  title-style = color: black;  font-weight: bold; text-align: left;| 
  content-style = color: black;  text-align: left; |
}}

[[Категорія:Розв'язник вправ по дискретній математиці]]