2-amaliy mashg‘ulot. Mavzu: Kengaytirilgan Yevklid algoritmi. Ishning maqsadi

2-amaliy mashg‘ulot.
Mavzu: Kengaytirilgan Yevklid algoritmi.
Ishning maqsadi: Kengaytirilgan algoritmi bilan ishlash va chiziqli diofant tenglamalarini kengaytirilgan Yevklid algoritmi yordamida umumiy va xususiy yechimlarini topishni o‘rganish.
Nazariy qism. Agar arifmetik butun sonlar ustida tenglik o‘rinli bo‘lsa soni sonini bo‘luvchisi deyiladi va kabi belgilanadi. sonining bo‘luvchilari deganda sonni bo‘luvchi noldan farqli barcha sonlarga aytiladi.

1-teorema. Butun a va b sonlari o‘zaro tub bo‘ladi, qachonki shunday butun u va v sonlari topilsaki, ular uchun au+bv=1 tenglik o‘rinli bo‘lsa.
Bu keltirilgan teoremani quyidagicha ham ifodalash mumkin: butun a va b sonlari o‘zaro tub bo‘lishi uchun, butun bo‘lgan s va t sonlari topilib, ular uchun as+bt=1 tenglikning bajarilishi zarur va yetarli.
Kengaytirilgan Yevklid algoritmida bir paytning o‘zida EKUB(a,b) ni hamda s va t o‘zgaruvchilarni hisolash imkoni mavjud. Algoritm oddiy Yevklid algoritmiga o‘xshash va uchta o‘zgaruvchilardan foyalanadi.
Quyidagi rasmda jarayon aks ettirilgan.

va o‘zgaruvchilar, oddiy Yevklid algoritmidan topiladi. O‘z navbatida qolgan o‘zgaruvchilarga boshlang‘ich qiymat beriladi.
Kengaytirilgan Yevklid algoritmini quyidagicha realizatsiya qilish mumkin.

O‘zaro tub sonlarni topish va ikki o‘zgaruvchili chiziqli diofant tenglamalarni yechish uchun kengaytirilgan Yevklid algoritmilan foydalaniladi.
Chiziqli diofant tenglamalar bu ikkki o‘zgaruvchilik ko‘rinishidagi tenglamalarga aytiladi.
Bizdan berilgan tenglasani yechish uchun x,y o‘zgaruvchilarni topish talab etiladi. Ushbu tipdagi tenglamalar bitta yechimni qabul qilmaydi. Shuning uchun ularda umumiy va xususiy yechimlar mavjud.
Agar berilgan bo‘lib, tenglik o‘rinli bo‘lsa, tenglama yechimga ega bo‘lmaydi. Agar tenglik bajarilsa, tenglama cheksiz ko‘p yechimga ega bo‘ladi. Ushbu yechimlardan biri xususiy, qolganlari umumiy yechimlar deyiladi.
X ususiy yechimlar:
Xususiy yechim topilgandan so‘ng umumiy yechimni topish mumkin.