Бардушкин В.В., Кожухов И.Б., Прокофьев А.А., Фадеичева Т.П. Основы теории делимости чисел. Решение уравнений в целых числах

Подождите немного. Документ загружается.

35333

=++ xyzxzyzxy .

Ответ: 1)

, ; 2) , , ; )1;1;2( )2;1;1( )1;2;2( )2;2;1( )2;1;2(

, ; )3;1;1( )1;3;1(

, , , , , ; )3;2;1( )2;3;1( )3;1;2( )1;3;2( )2;1;3( )1;2;3(

, , , , , . )3;2;1( )2;3;1( )3;1;2( )1;3;2( )2;1;3( )1;2;3(

8.43. Решите в целых числах уравнение:

; 2) . xyzzyx 2

222

=++ 382

=+− zyx

Ответ: 1)

; 2) нет решений. )0;0;0(

8.44. Решите в целых числах уравнение

yxxxx =++++



2003

... .

Ответ:

. )0;0(

8.45. Выясните, сколько решений в натуральных числах имеет система

⎪

⎩

⎪

⎨

⎧

nlk

mlk

Ответ: система решений в натуральных числах не имеет.

8.46. Сколько различных целочисленных пар

удовлетворяют

уравнению

);( yx

200254

+= yx?

Ответ: 30.

101

§ 9. Функция Эйлера

Важную роль в теории чисел играет функция Эйлера (1707–1783)

, значение которой для любого натурального числа п равно коли-

честву натуральных чисел, взаимно простых с

п и не превосходящих п,

т.е. количеству взаимно простых с

п чисел, расположенных в ряду

1, 2, … , п.

)(пϕ

Примеры.

1) Всеми числами, взаимно простыми с

20 и находящимися в ряду

1, 2, … , 20, являются: 1, 3, 7, 9, 11, 13, 17, 19. Поэтому

. 8)20( =ϕ

2) Для любого простого числа

р все натуральные числа, меньшие р,

взаимно просты с

р. Поэтому 1)(

−

=ϕ рр .

Лемма 8. Для любого простого числа р и любого натурального числа

k имеет место:

)1()(

−⋅=ϕ

−

ppр

Доказательство. Очевидно, что любое целое число взаимно просто с

тогда и только тогда, когда оно взаимно просто с р. Это означает,

что данное число не делится на

р.

В отрезке натурального ряда от

1 до содержится в точности

чисел, кратных р. Ими являются: . Все

остальные числа в данном отрезке не делятся на

р, а значит, взаимно

просты с

. Поэтому 

1−k

р pрррр

⋅

−1

,...,3,2,

р )1()(

−⋅=−=ϕ

−−

pppрр

kkkk

Отметим одно свойство, связанное с разбиением множества целых

чисел

Z на классы чисел по модулю т.

Пусть

(r = 0, 1, 2, … , m – 1) – какой-либо класс чисел по

модулю

т, состоящий из всех целых чисел, которые при делении с ос-

102

татком на

т дают в остатке r, т.е. из чисел, представимых в виде

qти += (q ∈ Z).

Так как

qmu

−= , то всякий общий делитель чисел и и т явля-

ется делителем чисел

т и r. Обратно, всякий общий делитель чисел т и

r есть делитель чисел и и т. Отсюда вытекает справедливость одного

из следующих двух утверждений:

1) Всякое число из

взаимно просто с т.

2) Ни одно число из

не взаимно просто с т.

Поэтому существует в точности

классов чисел по модулю

т, все числа которых взаимно просты с т. Эти классы называют вза-

имно простыми с модулем. Значит, в любой полной системе вычетов по

модулю

т содержится в точности чисел, взаимно простых с т.

Данное свойство (выделенное курсивом) будет использоваться при до-

казательстве леммы 9 о мультипликативности функции Эйлера.

)(тϕ

Лемма 9. Если N и , то ∈ba , 1),( =bаНОД

)()()( baba ϕ⋅ϕ=

⋅

Доказательство. Очевидно, можем считать, что

и , по-

скольку

1>а 1>b

1)1( =ϕ

Всякое натуральное число

и из отрезка натурального ряда

однозначно представляется в виде ba,...,3,2,1 rbxu

, где

; , при этом все числа указанного

вида содержатся в данном отрезке. Для наглядности дальнейших рассу-

ждений представим числа

в виде таблицы:

1,...,2,1,0 −= ax br ,...,2,1=

ba,...,3,2,1

1 2 3 … b

b + 1 b + 2 b + 3 … 2b

2b + 1 2b + 2 2b + 3 … 3b

…

… … … … …

a – 1

(a – 1) · b + 1 (a – 1) · b + 2 (a – 1) · b + 3 … ab

103

Пусть

х – фиксировано (в этом случае мы рассматриваем какую-то

определенную строку таблицы). Тогда числа

rbxu

( ) образуют полную систему вычетов по модулю b. br ,...,2,1=

Пусть

r – фиксировано (в этом случае мы рассматриваем какой-то

определенный столбец таблицы). Тогда числа

rbxu

(1) образуют полную систему вычетов по моду-

лю

а.

,...,2,1,0 −= ax

Согласно свойству, доказанному выше, среди чисел

rbxu

при каждом фиксированном значении

х содержится )(b

чисел, вза-

имно простых с

b, а при каждом фиксированном r содержится )(а

чисел, взаимно простых с

а.

Таким образом, в отрезке натурального ряда

со-

держится (в силу взаимной простоты чисел

а и b) в точности

чисел, которые одновременно взаимно просты и с а, и с b,

т.е. которые (см. § 1, лемма 4) взаимно просты с произведением

ab. Это

значит, что



ba,...,3,2,1

)()( ba ϕ⋅ϕ

)()()( baba ⋅ϕ=ϕ⋅ϕ

Замечание. Утверждение леммы неверно, если числа

а и b не являются

взаимно простыми. Например, при

, 2=а 4

b имеем: 1)2(

, , 2)4( =ϕ 2)4()2( =ϕ⋅ϕ 4)8()42(

ϕ=⋅ϕ . Таким образом,

, если . )()()( baba ⋅ϕ≠ϕ⋅ϕ 1),( ≠bаНОД

Теорема 16. Пусть натуральное число задано в каноническом

виде

1>п

pppn ⋅⋅⋅= ...

Тогда

)1(...)1()1(...)(

−⋅⋅−⋅−⋅⋅⋅⋅=ϕ

−

−−

ppppppn

Доказательство. Справедливость указанного равенства вытекает из

двух предыдущих лемм:

104

(

)

(

)

(

)

(

)

=ϕ⋅⋅ϕ⋅ϕ=⋅⋅⋅ϕ

kkk

pppppp ......

2121

)1(...)1()1(

−⋅⋅⋅−⋅⋅−⋅=

−

−−

pppppp



Пример. Найдите количество натуральных чисел, не превосходящих

числа

120 и взаимно простых с ним.

Решение.

. 32)15()13()12(532)532()120(

002113

=−⋅−⋅−⋅⋅⋅=⋅⋅ϕ=ϕ

Ответ:

32.

Отметим одно интересное свойство, связанное с функцией Эйлера.

Лемма 10. Для любого простого числа р и любого натурального k

выполняется равенство:

)(...)()()1(

2 kk

pppp ϕ++ϕ+ϕ+ϕ= .

Доказательство. Используя свойство

для про-

стого числа

р, имеем:

)1()(

−⋅=ϕ

−

ppр

=ϕ++ϕ+ϕ+ϕ )(...)()()1(

2 k

ppp

=−⋅++−⋅+−⋅+−+=

−

)1(...)1()1()1(1

pрррррр

kkkk

pppppppp =+−++−+−+−=

−−

)(...)()()11(

1122



Функция Эйлера используется в следующем соотношении Гаус-

са (1777–1855).

Теорема 17. Для любого натурального числа имеет место 1>п

∑

ϕ=

dп



)(

где суммирование производится по всем натуральным делителям

d чис-

ла

п.

Доказательство. Представим

п в каноническом виде:

pppn ⋅⋅⋅= ...

Тогда делителями

п являются всевозможные числа вида

105

ppp ⋅⋅⋅ ...

, где

kl ≤≤0 ),...,2,1( si

Используя уже известные свойства функции Эйлера, получим:

×ϕ++ϕ+ϕ+ϕ=⋅⋅⋅= ))(...)()()1((...

121

pррpppn

××ϕ++ϕ+ϕ+ϕ× ...))(...)()()1((

pрр

=ϕ++ϕ+ϕ+ϕ× ))(...)()()1((

sss

pрр

(

)

=⋅⋅⋅ϕ=ϕ⋅⋅ϕ⋅ϕ=

∑∑

≤≤≤≤

pppppp

)...()(...)()(

2121

∑

ϕ=



)(



Следующая теорема называется теоремой Эйлера. Она считается

одной из фундаментальных теорем теории чисел.

Теорема 18 (Эйлер). Если (1),( =паНОД

∈

а Z ), то

)(mod1

)(

па

≡

Доказательство. Пусть

, где

rrr ,,,

… )(nc

, – все числа из

совокупности

)1(,,3,2,1

−

п… , взаимно простые с п. Пусть r – одно

из чисел

. Тогда

rnqra +

⋅

=⋅ , . Если и п имеют об-

щий простой делитель

р, то

nr <≤

делится на р. Но это невозможно, т.к.

и . Следовательно, 1),( =паНОД 1),( =пrНОД 1),(

пrНОД

и число

содержится среди . Таким образом, для любого

индекса

i, , выполнено

rrr ,,,

…

сi ≤≤1

)(mod

)(

nrar

iai

≡

где

– некоторое число из совокупности . )(ia с,,3,2,1 …

Если

, то должно выполняться )()( iaja = )(mod narar

≡

, т.е.

)(

rran −⋅ . Поскольку , то 1),( =паНОД )(

rrn − . Но послед-

106

нее невозможно, т.к.

. Итак, набор чисел

есть некоторая перестановка чисел и

nrr

<−≤ ||1

)(,...,)2(,)1( сааа с,,2,1 …

)()2()1(21

...

caaac

rrrrrr

⋅

⋅=⋅⋅⋅ …

Перемножим теперь для всех

i, сi

≤

1 , сравнения

. Получим

)(mod

)(

nrar

iai

≡

)(mod...

2121

nrrrrrrа

⋅⋅⋅≡⋅⋅⋅⋅ …

Так как

1),...(

=⋅

⋅

⋅ пrrrНОД

, то по свойству сравнений

, т.е.  )(mod1 па

≡ )(mod1

)(

па

≡

Следствие (малая теорема Ферма). Если

р – простое число и ,

то

aр |

)(mod1

pа

≡

−

Доказательство. Так как

, то, согласно теореме Эйлера,



1)( −=ϕ рр

)(mod1

pа

≡

−

107

Упражнения

9.1.* Вычислите: 1)

; 2) ; 3) )1764(ϕ )2000(ϕ )261360(

Ответ: 1)

504; 2) 800; 3) 63360.

9.2. Найдите натуральное число

х, если:

; 2) ; 3) . 72)6( =ϕ

6912)12( =ϕ

1800)15( =ϕ

Ответ: 1)

3; 2) 4; 3) 3.

9.3. Найдите натуральное число

а, если для некоторых натуральных чи-

сел

т и п:

и ; 2) 108)( =ϕ а

пт

а 73 ⋅= 440)(

ϕ а и ;

пт

а 112 ⋅=

936)(

ϕ а и .

пт

а 133 ⋅=

Ответ: 1)

189; 2) 968; 3) 1521.

9.4.* Найдите количество натуральных чисел:

1) не превосходящих числа

605 и имеющих с этим числом наи-

больший общий делитель, равный

2) не превосходящих числа

1680 и имеющих с ним наибольший

общий делитель, равный

24.

Ответ: 1)

110; 2) 24.

9.5.* Докажите, что для любого целого числа

сумма всех нату-

ральных чисел, не превосходящих числа

т и взаимно простых с т, рав-

на

2≥т

)(5,0 тт ϕ⋅⋅

9.6.* Найдите все натуральные числа

п, для которых имеет место равен-

ство

)(2 пп

⋅= .

Ответ:

(

n 2=

∈

k N ).

9.7.* Докажите малую теорему Ферма (в обобщенной формулировке),

не опираясь на теорему Эйлера: если

р – простое число, то для любого

Z имеет место сравнение . ∈а )(mod pаа

≡

9.8. Найдите остаток от деления: 1)*

на 101; 2)* на 13;

100

на 17; 4)* на 24; 5)* на 385;

422

120

на 425; 7) на 7; 8)* на 132.

150

100100

43 +

10075

7453 ⋅+⋅

108

Ответ: 1)

1; 2) 12; 3) 9; 4) 21; 5) 155; 6) 375; 7) 1; 8) 7.

9.9.* Докажите, что при любом целом

п число делится на 42. пп −

9.10.* Докажите, что если целое число

а не делится на 5, то число

делится на 5. 1

−а

9.11.* Докажите, что если

p – простое число, то для любых целых чисел

а и b число делится на p тогда и только тогда, когда число

делится на p.

bа

−

ba −

9.12. Докажите, что если:

1)* число

делится на 7, то и число а делится на 7;

пт

аа

2) число

делится на 11, то и число а делится на 11.

пт

аа

1010

9.13.* Докажите, что если каждое из целых чисел

а и b взаимно просто

с числом

65, то число делится на 65.

1212

ba −

9.14. Докажите, что если целые числа

а и b взаимно просты, то:

1)* каждое из чисел

и не делится на 11;

2 ba +

2 ba −

2) каждое из чисел

и не делится на 7;

2 ba +

2 ba −

3) каждое из чисел

и не делится на 13.

2 ba +

2 ba −

9.15. Найдите все такие натуральные числа

п, что:

1)* число

делится на 7; 2) число 92 −

−

делится на 5.

Ответ: 1)

kп ; 2) kп 4

9.16.* Пусть

р и q – такие различные простые числа, что число 1

−

является делителем числа 1

−

q . Докажите, что для любого целого чис-

ла

а, взаимно простого с pq, имеет место сравнение

. )(mod1

pqа

≡

−

9.17.* Докажите, что если

р и q произвольные простые числа, то для

любого целого числа

а имеет место сравнение

. )(mod)( qpaqpapаq

⋅+≡+

9.18.* Пусть p и q – различные простые числа. Докажите, что в этом

случае имеет место сравнение

. )(mod1

pqqp

≡+

−−

109

ПРИЛОЖЕНИЕ 1

О решении уравнений в рациональных числах

К задаче решения в целых числах диофантовых уравнений тесно

примыкает задача отыскания всех рациональных решений подобных

уравнений. Она сама по себе довольно сложна и выделяется в отдель-

ный самостоятельный раздел математики. Несмотря на то, что рассмот-

рение теоретических и практических аспектов решения этой задачи вы-

ходит за рамки тематики данного

пособия, авторы посчитали нужным

затронуть (на примерах) те идеи, которые позволяют найти в рацио-

нальных числах все решения диофантовых уравнений второго порядка

от двух переменных.

Пример 1. Решите уравнение

в рациональных числах. 12

=− ух

Решение. Уравнение

задает на плоскости кривую второ-

го порядка (гиперболу). Найдем на кривой произвольную точку с ра-

циональными (!!) координатами. Это равносильно нахождению какого-

либо рационального решения исходного уравнения и обычно осуществ-

ляется методом подбора. Очевидное рациональное решение:

=− ух

)0;1();(

=ух

Всевозможные прямые, проведенные через точку

, могут

пересекать график кривой

не более, чем в одной точке

(это следует из теории кривых второго порядка).

);(

ух

=− ух

Заметим, что вертикальная прямая

не имеет других общих

точек с кривой

. Это равносильно тому, что при

1=х

=− ух 1

нет других рациональных решений исходного уравнения, кроме

. )0;1();(

=ух

Проведем через точку

прямую с угловым коэффициен-

том

k, ее уравнение в общем виде:

);(

ух

)(

xxkуу

−

⋅

− . В нашем

случае уравнение прямой будет

)1(

−

⋅

xky . Подставим

в уравнение , получим: )1( −⋅= xky 12

=− ух

110