Қазақстан республикасы білім және ғылым министрлігі павлодар мемлекеттік педагогикалық институты

 
94 
10.2 Арифметиканың негізгі теоремасы 
 
Кез  келген  құрама  санды  көбейту  көмегімен  кейбір  жай  сандардан  құрастыруға 
болады. Мысалы, 2009 құрама санды былай табуға болады: 
2009 = 7   7   41 
Математикада  арифметиканың  негізгі  теоремасы  қарастырылады,  ол  бойынша 
кез  келген  натурал  сан  (n>1)  не  өзі  жай  болады,  не  жай  бөлгіштердің  көбейтіндісіне 
жалғыз ғана тәсілмен жіктелу мүмкін (көбейткіштердің жол ретін еске алмағанда). 
Дәреже  белгіні  қолданып  2009  санды  жай  көбейткіштерге  жіктелуі  былай 
жазылады: 
2009 = 7
2
   41 
Көбейткіштерге  жіктеу  канондық  деп  аталады,  егер  барлық  көбейткіштер  жай 
болып өсу ретінде жазылатын болса.  
Мысалы, 150 санның көбейткіштерге канондық жіктелуін жазайық:  
150 = 2   3   5
2
 
 
10.3 Өзара жай сандар және Эйлер функциясы 
 
Екі сан өзара жай деп аталады, егер олардың бірден басқа ешқандай ортақ бөлгіші 
болмаса.  
Мысалы, 11 мен 12 сандар өзара жай (оларда бірден басқа ортақ бөлгіші жоқ),  30 
және 35 сандар — өзара жай емес (оларда ортақ бөлгіші 5 бар). 
Бүтін  сандармен  байланысты  заңдылықтарды  көп  зерттеген  болатын  швейцар 
математигі Леонард Эйлер (Leonard Euler). Олардың арасындығы: n-ды аспайтын және n-
мен  өзара  жай  болатын  қанша  натурал  сандар  бар?  Бұл  сұраққа  жауапты  Эйлер  1763 
жылы  тапты  және  осы  жауап  n  санның  жай  көбейткіштерге  канондық  жіктелуіне 
байланысты.  
Егер  
an
n
a
a
p
p
p
n
...
2
2
1
1
, 
мұндағы p
1
, p
2
,..., p
n
 – әртүрлі жай көбейткіштер, 
болса,  онда  n-нан  аспайтын  және  n-мен  өзара  жай  болатын    натурал  сандарды  былай 
табуға болады: 
n
p
p
p
n
n
1
1
...
1
1
1
1
)
(
2
1
 
n-нан  аспайтын  және  n-мен  өзара  жай  болатын  натурал  сандардың  саны  Эйлер 
функциясы деп аталады және белгіленеді  (n).  
Мысалы,  12-ден  аспайтын  және  12-мен  өзара  жай  болатын  натурал  сандар  саның 
табайық. Натурал сан қатарынан 
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 
12-мен  өзара  жай  болатын  тек  1,  5,  7,  11  сандар.  Олардың  саны  төртке  тең.  Сонымен 
(12)=4. 
Енді  (12)  Эйлер  формуласы  бойынша  есептеп  көрейік.  Ол  үшін  алдымен  12 
санның канондық жіктеуін жазамыз: 
12 = 2
2
 * 3. 
Эйлер функциясын  (12) есептейік:  
4
3
2
2
1
3
4
3
1
1
2
1
1
12
)
12
(
. 
Өзара  жай  сандарды  қарапайым  іріктеп  алудан  және  Эйлер  формула  бойынша 
есептелген мәндер сәйкес келеді.  

 
95 
Эйлер  формуласын  үлкен  n  үшін  пайдалану  ыңғайлы,  егер  n  санның  жай 
көбейткіштеріне  жіктеуі  белгілі  болса.  Криптографияда  Эйлер  формуласының 
маңыздылығы  –  жай  және  кейбір  басқа  сандар  үшін  (n)  санды  оңай  табу  мүмкіндігі. 
Криптографияда Эйлер формуласының келесі екі салдары пайдаланылады. 
1-ші салдары. Егер  p – жай сан, онда   (p) = p - 1. 
Шынында, егер  p – жай сан, онда оның канондық жіктеуі тек өзінен ғана тұрады. 
Сонда  
1
)
1
(
1
1
)
(
p
p
p
p
p
p
p
. 
2-ші салдары. р мен q — екі әртүрлі (р   q) жай сан болсын. Онда  
(p q) = (p – 1)(q – 1). 
Бұл формула келесі түрде түсіндіріледі. р q = N, мұнда р мен q — екі әртүрлі (р   q) жай 
сан болсын. Сонда 
)
1
(
)
1
(
)
1
(
)
1
(
1
1
1
1
)
(
)
(
q
p
q
p
q
p
q
p
q
p
N
N
q
p
. 
Эйлер формуласы пайдалануының бірнеше мысалдарын қарап шығайық. 
Мысал  1.    (13)  табайық.  13  –  жай  сан,  сондықтан,  1-ші  салдарды  пайдаланып 
(13)  =  13-1  =  12.    Өзімізді  (және  Эйлерді)  тексерейік,  ол  үшін  13-тен  кем  барлық 
сандарды жазып: 
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 
олармен өзара жай барлық сандарды санайық. Шынында олар 12. 
Мысал 2.    (35) табайық. 35 – құрама сан, демек бірінші салдары бізге келмейді. 
Бірақ  35  екі  жай  санның  көбейтіндісі:  35  =  5 7.    2-ші  салдарды  пайдаланып,  есептейміз 
(35):    
(35) = (5-1) (7-1) = 4 6 = 24. 
35 тен кем және онымен ортақ бөлгіштері жоқ барлық сандарды жазып тексереміз: 
1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 
27, 29, 31, 32, 33, 34. 
Шынында олардың саны 24.  
Соңғы  мысалдан  көрініп  тұр  –  көп  сандарды  қарастырғанша,  Эйлер  формуласын 
пайдалану ыңғайлы.  
 
10.4 Қалдықтар арифметикасы және салыстыру теориясы 
 
Неміс математигі Карл Фридрих Гаусс екі a мен b саны үшін 
a   b (mod m) 
жазуды  ұсынған  болатын,  егер  оларда  m-ға  бөлуден  бірдей  қалдықтары  бар  болса  (a 
модулі m бойынша b-мен салыстырлу деп оқылады). Мысалы, 
1997   1 (mod 4), 
7k + 1   1 (mod 7), мұндағы k – кез келген бүтін сан. 
Салыстыруларда  математиктар  мен  криптографтарға  пайдалы  қасиеттер  бар,  олар 
көбінесе теңдіктер қасиеттеріне ұқсайды. Бұл қасиеттер арифметикалық есептеулерді тым 
оңайлатады,  егер  бізге  тек  кейбір  m  санға  бөлудін  қалдығы  керек  болса.  Мысалы, 
салыстыру қасиеттер ашық кілті бар шифрлау алгоритмдағы есептеуде пайдалы.  
Салыстырулардың қарапайым қасиеттері келесі. 
1-ші қасиет. Егер a-b  m-ға бөлінсе, онда  a   b (mod m). 
Мысалы, 15   1 (mod 7), өйткені 15-1 = 14, ал 14  7-ге еселі. 
2-ші қасиет. Егер 
a   b (mod m) 
және