O’zbеkiston rеspublikasi oliy va o’rta maxsus ta'lim vazirligi

4.22-masala (Gauss ayniyati).
_ (d )  x
d|x
ayniyatni isbotlang.

Yechilishi. x  p^a1 p^a2 ... p^ak . Multiplikativ funksiyalar uchun asosiy ayniyatga

ko’ra,
₁ 2 k

_(d )  (1  ( p )  ( p² )  ...  ( p^a1 )... 

d|x
¹ 1 1

 {1  ( p  1)  ( p²  p )  ...  ( p^a1  p^{a1 1} )}... 

1 ₁ 1

 p^a1 p^a2 ... p^ak

1 1

 x _.

Ayniyat isbotlandi. ^▲

₁ 2 k

4.23-masala. Quyidagi tengliklarni isbotlang. a) (m) (n) = ((m, n)) ([m, n]);
b) (mn) ((m, n)) = (m) (n)(m, n).

Yechilishi. a) Multiplikativlikdan foydalanib, ^m va ⁿ sonlar bitta tub sonning darajalari bo’lgan holni qaraymiz: m = p^α, n = p^ ( 0). U holda (m) (n) =
((m, n)) ([m, n]) tenglik [m, n] = m = p^α, (m, n) = n = p^ tengliklardan kelib chiqadi.
b) Multiplikativlikdan foydalanib, m va n sonlar bitta tub sonning darajalari bo’lgan holni qaraymiz: m = p^α, n = p^ ( 0). Berilgan tenglik
(p^{α + }) (p^) = (p^α) (p^) p^.

tenglikka tengkuchli. Bu tenglik esa
( p^ )  p^{ 1} _ p 1_
tenglikdan kelib chiqadi. ^▲

5-§. Modulyar arifmetika


Ta’rif. mN , a,bZ sonlar berilgan bo’lsin. Agar a - b ayirma m soniga bo’linsa, u holda a soni b soni bilan m modul bo’yicha taqqoslanadi deyiladi va ushbu munosabat a  b (mod m) orqali belgilanadi.
m modulni fiksirlaymiz.
a = q₁t + r₁ , b = q₂ t + r₂ bo’lsin ( bu yerda r₁ , r₂ – qoldiqlar).
U holda

Haqiqatdan ham,
a  b (mod m)  m a  b
a  b (mod m)  r₁ = r₂


 m (m(q₁  q₂ )  r₁  r₂ )  m r₁  r₂ .

| r₂  r₁ || m | bo’lgani uchun bu faqat r₁ = r₂ bo’lgandagina bajariladi.


Xossalar. a  b (mod m) munosabat quyidagi xossalarga ega:

1. 
   a  a (mod m)
   
2. 
   a  b (mod m)  b  a (mod m)
   
3. 
   a  b (mod m) va b  c (mod m)  a  c (mod m)
   
4. 
   m modul bo’yicha taqqoslamalarni hadma-had qo’shish va ko’paytirish mumkin, ya’ni
   

_a  b(mod m) _{ }a  c  b  d (mod m)




^c  d (mod m) ^ ac  bd (mod m)

5. 
   Taqqoslamaning ixtiyoriy qismiga modulga karrali sonni qo’shish mumkin:
   

a  b (mod m) va k,l Z  a+km  b (mod m) va a  b+lm (mod m)

6. 
   Taqqoslamaning ikkala qismini bir xil natural darajaga ko’tarish mumkin:
   

a  b (mod m) va k N  a^k  b^k (mod m)

7. 
   Taqqoslamaning ikkala qismini bir xil butun songa ko’paytirish mumkin:
   

a  b (mod m) va k Z  ak  bk (mod m)

8. 
   x  y (mod m₁ ) va x  y (mod m₂ )  x  y (mod [m₁, m₂ ])
   
9. 
   x  y (mod m) va a_k Z ( k=0,1, ... , n) bo’lsa, u holda
   

a₀ xⁿ + a₁x^n-1 + ... + a_{n - 1} x + a_n  a₀ yⁿ + a₁ y ^n-1 + ... + a_{n - 1} y + a_n (mod m).

10. 
    x  y (mod m) va a_k  b_k (mod m) ( k=0,1, ... , n) bo’lsa, u holda
    

a₀ xⁿ + a₁x^n-1 + ... + a_{n - 1} x + a_n  b₀ yⁿ + b₁ y^n-1 + ... + b_{n - 1} y + b_n (mod m)

11. 
    (a, p)  1bo’lsin. ax  ay(mod p)  x  y(mod p)
    

12. 
    Agar a ≡ b(mod d), a ≡ b(mod c), (d,c) = 1 bo’lsa, u holda a ≡ b(mod dc).
    
13. 
    Agar a ≡ b(mod d) bo’lsa, u holda ixtiyoriy c  Z uchun ac ≡ bc (mod d).
    
14. 
    Agar ac ≡ bc(mod d) va (c,d) = 1 bo’lsa, u holda a ≡ b(mod d).
    

5.1-masala. Ixtiyoriy natural n son uchun quyidagilarni isbotlang:

1. 
   n²  0
   
2. 
   n²  0
   

yoki yoki
n²  1(mod 3) ;
n²  1(mod 5) ;

3. 
   n²  0
   

yoki
n²  1 yoki
n²  4(mod 8) ;

4. 
   n³  0 yoki n³  1(mod 9) ;
   

Yechilishi.

5. 
   n⁴  0
   

yoki
n⁴  1(mod 16) .

1. 
   Quyidagi hollarni qarab o’tamiz:
   

n  1,0,1(mod 3) . Bu hollarda n²  1,0,1(mod 3)

2. 
   Quyidagi hollarni qarab o’tamiz:
   

n  2, 1,0,1, 2(mod 3) . Bu hollarda


n²  1,1,0,1, 1(mod 3) .

Shunga o’xshab, c); d); e) lar ham tekshiriladi. ^▲

5.2-masala (Ferma⁶ teoremasi). p tub son uchun o’rinli bo’ladi.
а ^p  а(mod р) taqqoslama

Isbot. a bo’yicha induksiyani qo’llaymiz.
a  1
da natija ravshan. Faraz

qilamiz,
p | a ^p  a . U holda N’yuton binomi formulasiga ko’ra

(a  1)  (a  1)  (a  a)  _C a .
p1
p p k k p

p
p | C^k ,
k 1


k  1, 2,..., p 1 , munosabatdan (tekshiring) va induksiya faraziga ko’ra

p | (a  1) ^p  (a  1) . Demak, (a  1) ^p  (a  1)(mod p) . ^▲
Izoh. Agar (a, p)  1 bo’lsa, u holda Ferma teoremasidan quyidagi munosabat kelib chiqadi:
а^p1  1(mod р) .
Taqqoslamalarning xossalariga ko’ra quyidagiga egamiz:
c_i  d_i (mod p), i  1, 2,..., n  c₁c₂ ...c_n  d₁d₂ ...d_n (mod p) . (a, p)  1bo’lsin. Quyidagi sonlarni kiritamiz:
a, 2a,3a,...,( p 1)a .
bu ketma-ketlikda ikkita turli hadlari p modul bo’yicha taqqoslanmaydi. Haqiqatdan ham,

ia 
ja(mod p)  i 
j(mod p) 
j  i .

Demak,
a, 2a,3a,...,( p 1)a
sonlardan har biri 1, 2,3,..., p  1 sonlardan faqat bittasi

bilan p modul bo’yicha taqqoslanadi. Demak,

a  2a  3a ... ( p 1)a  a ^p1 1 2  3 ... ( p 1)  1 2  3 ... ( p 1)(mod p) .

⁶ Ferma P’er ( 1601-1655 y.y.) – fransiyalik advokat va matematik. Analitik geometriyaning asoschisi.

(1 2  3 ...  ( p 1), p)  1 bo’lgani uchun
a^p1  1(mod p)
bo’ladi. ^▲

5.3-masala.

topilsin.
ax  1(mod p) taqqoslamani qanoatlantiradigan barcha x sonlar

Yechilishi. Ferma teoremasiga ko’ra bu sonlar x  a^p-2 (mod p) taqqoslama bilan aniqlanadi. ^▲


5.4-masala. (Vilson⁷ teoremasi) ^p son tub bo’lsa, (^p - 1)! - 1(mod ^p) bo’ladi.
Yechilishi. {2,3,...., p – 2} sonlar to’plamini qaraymiz. Oldingi masalaga

ko’ra bu to’plamdagi ixtiyoriy a son uchun
ab  1(mod p) taqqoslamani

qanoatlantirdigan va shu to’plamga tegishli bo’lgan a dan farqli yagona b son topiladi. {2,3,...., p – 2} to’plamdagi barcha sonlarni juft-jufti bilan ko’paytirib chiqsak,

ni hosil qilamiz. Bundan

1 2  3 ... ( p  2)  1(mod p)

kelib chiqadi. ^▲

( p 1)!  ( p  2)!( p  1)  ( p  1)  1(mod p)