* Данный текст распознан в автоматическом режиме, поэтому может содержать ошибки

280 ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ Пример. 9(10) = 4; 3* = 8 1 = l ( m o d 10); 7* = 2401 = = l ( m o d 10). В частном случае, когда модулем служит простое число р в ряду 1, 2, . . . , р взаимно простыми с р будут все числа, кроме р; таким образом, ср(р)=р — 1; соответствующий случай теоремы Эйлера был ранее доказан Фермб. Т е о р е м а Ф е р м & . Если р — простое число и а не делится на р то аР- — \ (mod р). % % х Примечание. Это предложение часто называют «малой теоремой Ферма» в отличие от так называемой «великой теоремы Ферма» о невозможности решения в целых положительных чи­ слах уравнения х* У = при целом п ^ > 2 (это утвержде¬ ние, доказательством которого Ферма, по его свидетельству, обла­ дал, как известно, не доказано до настоящего времени). Если изме­ рять важность той или другой теоремы её ролью и значением в развитии данной отрасли науки, то следовало бы, пожалуй, при­ нять обратную терминологию. Если «великая» теорема когда-либо будет доказана, то сам этот факт, насколько здесь возможно пред­ видение, не даст науке никакой опорной точки для значительных новых достижений и, по всей вероятности, останется более или менее изолированным; Напротив, установленная нами «малая» тео­ рема уже давно стала важнейшим орудием исследования и притом не только в теории целых чисел, но и в значительно более широких областях арифметики и алгебры. Мы переходим теперь к установлению вида функции ср (т), означающей число натуральных чисел, не превосходящих т и вза­ имно простых с т. Прежде всего мы докажем, что если числа тип взаимно про­ сты, то ер (тп) = <р (т) <р (л). Чтобы подсчитать <р (тп), удобно расположить числа от 1 до тп в следующую таблицу: 1 m-f-1 2т-\-\ (п—1)те-(-1 т-\-2 2 /га 2 ... 2 ... m-\-k 2m-{-k (п—l)m-{-k ... ... натуральные * k m 2т Зт пт (я—1)/и + 2 и постараться определить, сколько эта таблица содержит чисел, взаимно простых с произведением тп. Но для того, чтобы быть