Теория чисел

лучим числа, меньшие JV и не делящиеся Hap1; число их JV1. Значит JVi = J V ^ l — у - ) , и формула верна для / = 1; значит она верна для любого I. Теорема Гаусса. Если каноническое разложение числа N имеет вид: N=P1aiP29*... рт\ то tw-e-iX'-a-i1-= Д о к а з а т е л ь с т в о . Число N делится на P1, на р2, . . . , на рш. Согласно доказанной лемме чисел, меньших JV и не делящихся на P i i f t . · · · > ΡΜ. будет: « • - · < - * ) ( ' - * ) - ( ' - а -Покажем, что эти числа совпадают с числами, меньшими. JV и с ним взаимно простыми: 1°. Каждое из чисел, меньших JV и не делящихся на P1, на р2, . . . , н а рт, есть взаимно простое с JV. Предположим противное: пусть Jli (JÜ «< JV) не делится на pv р2, . . . , рт и (JV1Jli) = d > 1. Обозначим наименьший простой делитель d через р . Так как JV-:р, то ρ равно одному из чисел pv р2, . . . , рт, и Jli делится на это число, что невозможно. 2°. Каждое из чисел, меньшее JV и взаимно простое с JV, не де­лится на pv на р2, . . . , н а рт о, следовательно, числа, меньшие JVnHe делящиеся на рир2>... , рт, — это числа, меньшие JV и с ним взаимно простые. Значит φ (N) = Jvf 1 — . . . — γ-j, и теоре­ма доказана. П р и м е р 1. φ(24) = φ ( 2 ^ 3 ) = 2 4 ^ 1 — ( l — ^) = 8-Действительно, числа, меньшие 24 и с ним взаимно простые, следующие: 1, 5, 7, 11, 13, 17, 19, 23. Следствие. Если N=pa, то φ (JV) = N(l — ~^=ра (l — -J-)— = P5 t - Pa " 1. Теорема. Если (а,Ъ) = 1, то φ (ab) = φ (α) φ(&). Д о к а з а т е л ь с т в о . Пусть даны канонические разложения чи­сел а и Ь: & = Pi Pa * · •Pn > Так как (а, Ъ) = 1, то ни одно из чисел P p P2, . . . > РЯ не Р^вно Следовательно, αϊ» = P1"1, р2*а -. - PhM ip i^ sp" · · · 2mP m-до