Эйлер функциясы. Эйлер және Ферма теоремалары
Эйлер функциясы барлық натурал сандар үшін анықталады және а- мен өзара жай 1,..,а-1 сандар қатарынан алынады.
Теорема.
Егер - а санының канондық түрдегі жіктелуі болса, онда
2 теорема.
р – жай сан болсын, , онда
Эйлер және Ферма теоремалары барлық салыстыоулар теориясының негізі болып табылады, теориялық зерттеулерде де, арифметикалық қосымшаларда да кеңінен қолданылады.
Мысал.
Эйлер теоремасы.
Егер (a,m)=1 a (I)
Эйлер теоремасын m=p – жай сан болған кезде қарастырамыз. Бұл жағдайда φ(p)=p-1, сондықтан келесі теорема шығады.
Ферма теоремасы . Егер р – жай сан болса және саны р –ға бөлінбейтін бүтін сан болса, онда
(,p)=1, то (II)
Ферма теоремасының басқаша айтылуы: (Салдар)
Егер р – жай сан болса, онда кез келген бүтін саны үшін келесі теңдік орын алады
Расында да,
а) егер (а,р)=1 (II) салыстырудың екі жағын да -ға көбейтіп, аламыз.
б) егер (а,р)≠1, онда да р –ға бөлінеді, яғни
Бір белгісізі бар бірінші дәрежелі салыстырулар
Кез келген бір белгісізі бар бірінші дәрежелі салыстыруды келесі түрге келтіруге болады:
ах b (mod m) (I)
a 0 (mod m)
(I) салыстыруының жалғыз шешімі, бірнеше шешімі, мүлде шешімі болмауы мүмкін.
1 теорема. Егер (a,m) = 1 болса, онда (1) салыстыруының шешімі бар және жалғыз болады.
2 теорема. Егер (a,m)=d>1 және b d-ға бөлінбесе , онда (1) салыстыруының шешімі жоқ.
3 теорема. Егер (a,m)=d>1 және bd, онда (1) салыстырудың d әртүрлі шешімі бар болады. Бұл шешімдердің барлығы модулі бойынша бір класс құрайды.
Достарыңызбен бөлісу: |
