Эйлер функциясы туралы қазақша реферат
Айталық, m = p1α1p2α2 … ptαt , m>1натурал санының Канондық жіктелуі болсын.
φ (m) = p1α1-1(p1-1)p2α2-1(p2-1) … ptαt -1(pt-1) және φ(1) = 1 болсын.
Сонымен натурал аргументті φ функциясын анықтаймыз.
Анықтама 1 Жоғарыда көрсетілген әдіспен анықталған φ функциясы Эйлер функциясы деп аталады.
Анықтама 2 Эйлер функциясы n-нан кіші және n-мен өзара жай оң бүтін сандардың санына тең функцияны атайды. Функция φ(n) деп белгіленеді.
Мысалға, φ (10) = 4. Эйлер функциясының келесі тамаша қасиеті бар: егер n = pq, мұндағы p және q – жай сандар, онда φ(n) = (p-1)(q-1)-ге тең болады.
Теорема 1 (Эйлер) Кез-келген n модулі мен n-мен өзара жай а саны үшін келесі салыстыру ақиқат
aφ(n)-1 ≡ 1(mod n)
Анықтама 3 Келесі үш шартты қанағаттандыратын θ функциясын мультипликативті деп атаймыз:
1) θ кез келген натурал сан үшін анықталған;
2) θ(1) = 1;
3) егер (a,b) = 1 болса, онда θ(ab) = θ(a)θ(b).
Теорема 2 Эйлер функциясы – мултипликативті функция.
Дәлелдеуі. Айталық, p1α1… ptαt және q1β1 … qsβs сәйкесінше өзара жай натурал m1>1 және m2>1 өзара жай сандарының канондық жіктеулері болсын. Онда p1, …, pt сандарының әрқайсысы q1, …, qs сандарының әрқайсысына өзгеше. Бұдан m1m2 канондық жіктеуі p1α1… ptαt q1β1 … qsβs. φ (m1m2) = φ (m1) φ (m2) теңдеуі, Эйлер функциясының анықтамасынан тікелей шығады. m1 = 1 немесе m2 = 1 үшін берілген теңдеу айқын. Теорема дәлелденді.
Теорема 3 φ (m) саны 1, 2, …, m сандық тізбегіндегі m-мен өзара жай болатын сандардың санына тең.
Дәлелдеуі. Дәлелдеме m>1 санының канондық жіктеуіндегі жай көбейткіш сандардың саны n бойынша математикалық индукция әдісі бойынша жүргізіледі. Теорема n = 0 (m = 1) және n = 1 (m = p) үшін орындалады, мұндағы p – жай сан. Айта кетерлік жайт, i натурал саны mp–мен өзара жай болу үшін ол бір мезгілде m мен p сандарымен өзара жай болуы қажет және жеткілікті. 1, 2, …, mp тізбегін талдау үшін ұзындығы m-ге тең p тізбекшелеріне mk+1, mk+2, …, mk+m-бөлеміз, мұнда k = 0, 1, …, p-1. Теорема 3-тен (mk + i,m) = (i, m) шығады. Осы теңдік пен осы индуктивті ұйғарымнан mk+1, mk+2, …, mk+m тізбекшесінде m–мен өзара жай φ (m) сан бар. Осыдан 1, 2, …, mp тізбегінде m–мен өзара жай φ (m)p сан бар. M p-ға бөлінетін жағдайда, бұл сандар p-мен өзара жай, сонымен қатар mp санымен де өзара жай. Соңғы ескерту мен айқын теңдік φ (mp) = φ (m)p қарастырылған жағдайдағы теореманың ұйғарымын дәлелдейді.
m-нің p-ға бөлінбейтін жағдайын қарастыру қалды. m-мен өзара жай φ (m)p сандарының санынан осылардың p-ға бөлінетіндерінің санын алып тастасақ, іздеген φ (mp) санын табамыз. Ол сандар тек p, 2p, 3p, …, mp сандарының арасында ғана болуы мүмкін. Сондықтан, m-мен өзара жай сандардың арасындағы p-ға бөлінетіндерінің саны p, 2p, 3p, …, mp сандарының арасындағы m-мен өзара жай сандардың санына тең болады. Егер i≤m және (m,p) = 1 болғанда (ip,m) = (i,m) болатынын ескерсек, онда p, 2p, 3p, …, mp сандарының арасындағы m-мен өзара жай сандар саны. 1, 2, …, m сандарының арасындағы m-мен өзара жай сандар санына тең, яғни индукция бойынша φ (m). Қорыта келе, ізделінді φ (mp) = φ (m)p — φ (m) = φ (m)(p-1). Теорема дәлелденді.
Эйлер функциясының осы қасиетінің берілген дәлелдемесін Р.А.Сүйіндіков ұсынды.
Мысалдар: Берілген n натурал саны жай сан деп саналады, егер де ол тек өзіне ғана және 1-ге бөлінетін жағдайда a, n 2 натурал сандар өзара жай сандар деп саналады, егер олардың ортақ бөлгіштері болмаса.
1. n = 7
1 2 3 4 5 6 j(7) = 6.
2. n = p*q, p,q –жай сандар, j(n) = (p-1)*(q-1)
n = 33 = 11*3, j(33) = (11-1)(3-1) = 20.
3. n = kr
j(n) = (k-1)*kr-1, n = 8 = 23
j(8) = (2-1)*23-1 = 1*4 = 4.