Mirzo ulug’bek nomidagi

Nazorat uchun savollar:

1. 
   Evklid usuli qayerda qo‘llaniladi?
   
2. 
   Bu usul nima uchun Evklid algoritmi deyiladi?
   
3. 
   Qanday sonlarning EKUB i birga teng?
   
4. 
   Qanday sonlarning EKUB i ulardan biriga teng? Mustaqil ish uchun misollar.
   

Quyida keltirilgan sonlarning EKUB i topilsin:
1. (21,35)=?
2. (42,180) =?
3. (258,312) =?
4. (1024,512) =?
5. (83,279) =?
6. (191,1021) =?
7. (415,747) =?
Agar n > 1 natural son bo‘lsa, quyidagilarni isbot qiling:
1. (n,2n+1)=1
2. (2n+1,3n+1)=1
Berilgan natural son p>1 tub deyiladi, agarda bu son o‘zi p va 1 dan boshqa natural songa bo‘linmasa. Misol uchun: 2,3,5,7,11,13,17,19,23,29, tub sonlar, ularning soni cheksiz davom etadi.
Barcha butun sonlarni modul deb ataluvchi - biror fiksirlangan natural n soniga bo‘lganda qoladigan qoldiqlar bilan bog‘liq holda o‘rganamiz. Bunda elementlari soni cheksiz bo‘lgan barcha butun sonlar to‘plamiga, 0 dan n-i gacha bo‘lgan butun sonlarni o‘z ichiga oladigan chekli, quvvati n ga teng bo‘lgan
{0;1;2;3;...;n-l} - to‘plam mos qo‘yiladi. Bu quyidagicha amalga oshiriladi: a va
n -natural sonlar bo‘lsa, "a sonini n soniga qoldiq bilan bo‘lish", deganda ushbu
a =q n + r
tenglik tushuniladi. Bu yerda 0 <r< n, shartni qanoatlantiruvchi natural q va r sonlarini topish tushuniladi. Bu oxirgi tenglikda qoldiq deb ataluvchi r soni nolga teng bo‘lsa r=0, natural a soni n soniga butun bo‘linadi yoki n soni a sonining bo‘luvchisi deyiladi.
Butun a va b sonlari modul n bo’yicha taqqoslanadigan deyiladi, agarda
ularni n ga bo‘lganda qoladigan qoldiqlari teng bo‘lsa, a = b mod n deb yoziladi. Bundan esa, a va b sonlar ayirmasining n ga qoldiqsiz bo‘linishi kelib chiqadi.
Qoldiqni ifodalash uchun ushbu b=a mod n tenglikdan foydalaniladi hamda b=a mod n tenglikni qanoatlantiruvchi b sonini topish a sonini modul n bo’yicha keltirish deyiladi. Ixtiyoriy butun b soni uchun ushbu
M={a₀,a_l...,a_n-l : 0_k k=0,1,...,n-1}
to‘plamga tegishli a_k=b mod n munosabatni qanoatlantiruvchi son a_k, k = {0,1,..., n-l}, mavjud bo‘lsa, M to‘plam modul n bo‘yicha to‘liq chegirmalar tizimi deyiladi. Ko‘rinib turibdiki, to‘liq chegirmalar tizimi M={a₀,a_i,...,a_n4: 0<a_k k=0,1,...,n-1}.
Biror n modul bo‘yicha qo‘shish, ayirish va ko‘paytirish amallariga nisbatan quyidagi kommutativlik, assotsiativlik va distributivlik munosabatlari o’rinli: (a+b)mod n=((a mod n)+(b mod n))mod n,
(a-b)mod n=((a mod n)-(b mod n))mod n, (ab)mod n=((a mod n)·(b mod n))mod n, (a(b+c))mod n=((ab) mod n+(ac) mod n)mod n.
Butun a va b sonlari o‘zaro tub bo‘ladi faqat va faqat shundaki, qachonki shunday butun u va v sonlari topilsaki, ular uchun au+bv=1 tenglik o‘rinli bo‘lsa.
Agarda butun a va v sonlari o‘zaro tub bo‘lsa, ya’ni (a,n)=1 bo‘lsa, u holda ushbu (ab)mod n=1 munosabatni qanoatlantiruvchi butun b soni mavjud bo‘lib, bu b son a soniga modul n bo’yicha teskari deyiladi, hamda, b = a⁴ mod n deb belgilanadi.
Teskari elementni hisoblashning yana bir usulini keltiramiz. Berilgan n soni bilan o‘zaro tub bo‘lgan (1;n) oraliqdagi barcha elementlarning soni bilan aniqlanuvchi F(n) funksiyaga Eyler funksiyasi deyiladi va u quyidagicha aniqlanadi:

1. 
   F (n)=n-1, agar n tub bo‘ lsa;
   
2. 
   F(n)=(p-1)(q-1), agar n=pq bo‘lib, p va q sonlar tub bo‘lsa;
   

3. F(n)=n(1-1/p1)(1-1/p2) (1-1/p_k),

agar ^∏𝑘 𝑃^𝑡𝑖 𝑖, 𝑡 ∈ 𝑁, 𝑝

⁽𝑖 = 1, … , 𝑘⁾ -tub sonlar.

^𝑖=1 𝑖 ^{𝑖 𝑖}
Eyler teoremasi. aa^n-1mod n = 1 tenglik o‘rinli. Demak, (a,n)=1 bo’lsa, a^-1=a^F(n)-1mod n tenglik o’rinli.
Fermaning kichik teoremasi. n - tub son bo‘lib, aa^n-1 mod n=1 tenglik o‘rinli.
Agar a va n sonlari o‘zaro tub bo‘lsa, a^-1 =x mod n tenglama yagona yechimga ega bo‘ladi;
Agar a va n sonlari o‘zaro tub bo‘lmasa, a^-1 = x mod n tenglama yechimga ega emas.
Bevosita hisoblashlar asosida, ushbu (a* x) mod n = b tenglama a,n,b - sonlarining qanday qiymatlar qabul qilishiga qarab, yoki bir nechta yechimlarga ega bo‘lishi mumkinligiga, yoinki bitta ham yechimga ega bo‘lmasligiga ishonch hosil qilish mumkin.