3 Эйлер функциясы. Эйлер және Ферма теоремалары Эйлер функциясы барлық натурал сандар үшін анықталады және а- мен өзара жай 1,..,а-1 сандар қатарынан алынады.
Теорема.
р – жай сан болсын, , онда
Эйлер және Ферма теоремалары барлық салыстыоулар теориясының негізі болып табылады, теориялық зерттеулерде де, арифметикалық қосымшаларда да кеңінен қолданылады.
Мысал.
Эйлер теоремасы.
Егер (a,m)=1 a (I)
Эйлер теоремасын m=p – жай сан болған кезде қарастырамыз. Бұл жағдайда φ(p)=p-1, сондықтан келесі теорема шығады.
Ферма теоремасы . Егер р – жай сан болса және саны р –ға бөлінбейтін бүтін сан болса, онда
