Қазақша рефераттар

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

Эйлер функциясы: анықтамалар және негізгі формула

Айталық, m > 1 натурал санының канондық жіктелуі m = p1α1 p2α2 … ptαt болсын. Мұнда p1, …, pt — жай сандар, ал α1, …, αt — натурал көрсеткіштер.

Негізгі формула

φ(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, өйткені 1, 3, 7, 9 сандары 10-мен өзара жай.

Эйлер функциясының маңызды қасиеттерінің бірі: егер n = pq, мұндағы p және q — жай сандар болса, онда φ(n) = (p-1)(q-1).

Эйлер теоремасы

Теорема 1 (Эйлер)

Кез келген n модулі және n-мен өзара жай a саны үшін келесі салыстыру ақиқат:

aφ(n) ≡ 1 (mod n)

Мультипликативті функция және φ(n)-нің қасиеті

Анықтама 3

Келесі үш шартты қанағаттандыратын θ функциясын мультипликативті деп атаймыз:

  • θ кез келген натурал сан үшін анықталған;
  • θ(1) = 1;
  • егер (a,b) = 1 болса, онда θ(ab) = θ(a)θ(b).

Теорема 2

Эйлер функциясы — мультипликативті функция.

Дәлелдеудің қысқаша сұлбасы

m1 > 1 және m2 > 1 өзара жай натурал сандар болсын. Олардың канондық жіктеулеріндегі жай көбейткіштер бір-бірінен өзгеше.

Сондықтан m1m2-нің канондық жіктелуі екі жіктеудің бірігуінен тұрады, ал Эйлер функциясының анықтамасынан тікелей: φ(m1m2) = φ(m1)φ(m2). m1=1 немесе m2=1 жағдайы айқын.

φ(m) санының комбинаторлық мағынасы

Теорема 3

φ(m) саны 1, 2, …, m тізбегіндегі m-мен өзара жай болатын сандардың санына тең.

Дәлелдеудің идеясы (индукция)

Дәлелдеу m санының канондық жіктелуіндегі жай көбейткіштердің саны бойынша математикалық индукция әдісімен жүргізіледі. Негізгі жағдайлар: m=1 және m=p (мұндағы p — жай сан).

Маңызды байқау: i натурал саны mp-мен өзара жай болуы үшін, оның бір мезетте m және p сандарымен өзара жай болуы қажетті әрі жеткілікті.

1,2,…,mp тізбегін ұзындығы m болатын p ішкі тізбекке бөлеміз: mk+1, mk+2, …, mk+m, мұнда k=0,1,…,p-1. Бұл жерде (mk+i, m) = (i, m).

Екі жағдай қарастырылады:

  • Егер p | m болса, онда φ(mp) = φ(m)p.
  • Егер p ∤ m болса, онда p-ға бөлінетін, бірақ m-мен өзара жай элементтердің санын алып тастау арқылы φ(mp) = φ(m)(p-1) формуласы алынады.

Ескерту: осы қасиеттің берілген дәлелдеу нұсқасын Р. А. Сүйіндіков ұсынған.

Анықтамалық ескертпелер және мысалдар

Жай сан

n натурал саны жай сан деп аталады, егер ол тек 1-ге және өзіне ғана бөлінсе.

Өзара жай сандар

a және n натурал сандары өзара жай деп аталады, егер олардың ортақ бөлгіші 1-ден өзге болмаса.

Белгілеу

Кейбір әдебиеттерде φ(n) орнына j(n) белгілеуі де қолданылады.

Есептелген мысалдар

  1. 1) n = 7

    1, 2, 3, 4, 5, 6 сандары 7-мен өзара жай, сондықтан φ(7) = 6 (яғни j(7)=6).

  2. 2) n = pq (p, q — жай сандар)

    φ(n) = (p-1)(q-1).

    Мысалы, 33 = 11·3, сондықтан φ(33) = (11-1)(3-1) = 20 (яғни j(33)=20).

  3. 3) n = pr (жай санның дәрежесі)

    φ(pr) = (p-1)pr-1.

    Мысалы, 8 = 23, сондықтан φ(8) = (2-1)·23-1 = 1·4 = 4 (яғни j(8)=4).