Olimpiada masalalari

Noaniq tenglamaning bitta yechimi deganda, berilgan tenglamani to‘g‘ri tenglikka aylantiradigan noma’lum qiymatlar to‘plami tushuniladi.
Tenglama ax + by = c ko‘rinishida bo‘lib, bu yerda a, b, c – noldan farqli butun sonlar.


1- tasdiq. Agar EKUB (a; b) = d, u holda tenglama o‘rinli bo‘ladigan x va y sonlar mavjud.
(Bu tenglama chiziqli kombinatsiya yoki ikki sonning eng katta umumiy bo‘luvchisini sonlarning o‘zi orqali chiziqli ifodalash deyiladi).
2-tasdiq. Agar ax + by = l (a, b) = 1 bo‘lsa, u holda tenglama kamida bitta butun yechimga ega.
Bu tasdiqning to‘g‘riligi 1-tasdiqdan kelib chiqadi. Agar (а, b) = 1 bo‘lsa, u holda ах + by = 1 tenglamaning bitta butun yechimini topish uchun 1 ni a va b sonlarining chiziqli kombinatsiyasi ko‘rinishida ifodalash yetarlidir.
121-misol. 15x + 37y = 1 tenglamaning butun yechmini toping.


Yechish

1) Evklid algoritmini qo‘llaymiz va EKUB (15, 37) ni topamiz:

EKUB(15, 37) = 1

2) 1 ni oxiridan boshlab ketma-ket ravishda olingan tenglamalardan foydalanib, to‘liqsiz bo‘linma va qoldiqlar orqali ifodalaymiz:
, ya’ni
x₀ = 5, y₀ = -2.
3-tasdiq. Agar х + by = с tenglamada (а, b) = d > 1 bo‘lsa va c d ga bo‘linmasa, u holda tenglama butun yechimlarga ega emas.
122-misol. 16x - 34y = 7 tenglamaning butun yechimini toping.


Yechish

(16, 34) = 2, 7 -2 ga bo‘linmaydi, tenglama butun yechimlarga ega emas.

4-tasdiq. Agar ах + by = с tenglamada (a, b) = d > 1 va c d ga bo‘linsa, u holda u а₁х + b₁у = c₁ tenglamaga teng kuchli, bunda (a₁, b₁) = 1.
5-tasdiq. Agar ах + by = с tenglamada (а, b) = 1 bo‘lsa, u holda bu tenglamaning barcha butun yechimlari

formularda jamlanadi, bu yerda x₀, y₀ - ах + by = 1 tenglamaning butun yechimi, t – ixitiyoriy butun son.
Keltirilgan tasdiqlar ах + by = с (bu yerda (а, b) = 1) tenglamaning butun sonlardan iborat yechimlarini topish uchun quyidagi qonuniyatlarni o‘rnatishga imkon beradi: