Эйлер функциясы

Эйлер функциясы туралы қазақша реферат

Айталық, m = p₁^α₁p₂^α₂  …  p_t^α_t   , m>1натурал санының Канондық жіктелуі болсын.

φ (m) = p₁^α₁^-1(p₁-1)p₂^α₂^-1(p₂-1)   …  p_t^α_t ^-1(p_t-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 Эйлер функциясы – мултипликативті функция.

Дәлелдеуі. Айталық, p₁^α₁…  p_t^α_t    және q₁^β_{1 …} q_s^β_s  сәйкесінше өзара жай натурал m₁>1 және m₂>1 өзара жай сандарының канондық жіктеулері болсын. Онда p₁, …, p_t сандарының әрқайсысы q₁, …, q_s сандарының  әрқайсысына өзгеше. Бұдан m₁m₂ канондық жіктеуі p₁^α₁…  p_t^α_t   q₁^β_{1 …} q_s^β_s. φ (m₁m₂) = φ (m₁) φ (m₂) теңдеуі, Эйлер функциясының анықтамасынан тікелей шығады. m₁ = 1 немесе m₂ = 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 тізбекшелеріне m_k+1, m_k+2, …, m_k+m-бөлеміз, мұнда k = 0, 1, …, p-1. Теорема 3-тен (mk + i,m) = (i, m) шығады. Осы теңдік пен осы индуктивті ұйғарымнан m_k+1, m_k+2, …, m_k+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 = k^r

j(n) = (k-1)*k^r-1, n = 8 = 2³

j(8) = (2-1)*2^3-1 = 1*4 = 4.