Deza_Kotova_Sbornik_zadach_po_teorii_chisel

а)

7х =

lO(mod 13);

е)

40х = 60(mod44);

б) 2х =

12(mod 17);

ж)

18х = 45(mod65);

в)

7х =

12(mod 47);

з)

lOx = 15(mod 55);

r) 8х = 50(mod61);

и)

30х = 42(mod 102).

д)

24х = 20(44);

5.

Укажите число решений сравнения:

а) х6 =23(mod13);

r)

х6 = 53(mod 97);

б) 2х10 =25(mod17);

д)

х10

= 25(mod 53);

в) 5х20 =34(mod19);

е) х20

= 15(mod 61).

6.

Решите сравнение:

ж) 32х28 =SO(mod 61);

а)

31х6 = 20(mod 73);

б)

36х12

= 16(mod 79);

з) 5Ох

50 =SO(mod 47);

в)

16х18

= 24(mod97);

и) 3z =7(mod 11);

г)

12х18

= 54(mod 13);

к)

6z = -3(mod 13);

д)

16х82 = 32(mod 1.?);

л)

152z = -3(mod 61);

е)

77х77

= 33(mod 19);

м) gz = -3(mod 47).

7.

Найдите остаток от деления:

а) 100300 на 13;

д) 300500 на 19;

б) 100300 на 47;

е) 400300 на 47;

в) 100300 на 41;

ж) 100200 на 61;

г)

200400

на 17;

з)

21 49

на 97.

§ 21. Индексы

1з1

8.

Найдите остаток от деления:

а) 293010 на 71;

д) 556611 на 73;

б) 491020 на 67;

е) 345678 на 79;

в) 373219 на 83;

ж) 333333333 на 59;

г) 442233 на 61; ,

з) 22222222 на 53.

9.

Найдите все индексы:

а) числа 7 по модулю 13;

в) числа 20 по модулю 17;

б) числа 4 по модулю 7;

г) числа 50 по модулю 19.

10.

Найдите:

а)

Р1(12);

в)

Р17(4);

д)

Р61(12);

б)

Р13(22);

г)

P19(ll);

е)

Р41(2).

кривая:

а) 19у = 3х4 + 22;

б) 13у = 3х2 + 20.

132

Глава 1. Задачи по курсу теории чисел

15.

Сколько решений имеет сравнение:

а) х12

=l(mod 77);

ж) х15 =l(mod 143);

б)

х12

=l(mod 91);

з) х60 =79(mod 97);

в)

х12

=l(mod 143);

и)

х18

= l(mod 77);

г) 3х12 =3l(mod 41);

к)

х18

=l(mod 91);

д) х15 =l(mod451);

л) х18

=l(mod143);

е)

х15

=l(mod 287);··

м)

х55

=17(mod 97)?

16.

Решите сравнение:

14х15 =39(mod61);

а)

315х =520 (mod 7);

ж)

б) 220х =4(mod 101);

з) 32х

333 =23(mod 205);

в)

320х =-4(mod 29);

и)

132х42

=

51(mod 61);

г)

2х13 =5(mod 19);

к)

156х108

=

-63(mod 101);

д) 71х12

=lO(mod 97);

л)

l9x

25 =39(mod 61);

е) 27х13

=16(mod 79);

м) 73х18

=

17(mod 67);

§ 21.

Индексы

133

н) 27х49 =23(mod 71);

п) 16х35 =27(mod43).

о)

16х30 =18(mod 73);

17.

Решите сравнение:

а) 7(х + 5)28 =ЗO(mod 61);

б) -10(2х - 4) 16 =17(mod 31);

в)

34(х + 45)55 =7(mod 59);

г) 65(х -

1) 14 =39(mod 59);

д) 3х2 + 4х + 7 =O(mod 31);

е)

ioz =l(mod 41·31);

ж) 9х2 + 45х - 36 =O(mod 3 · 23);

з) 25х35 =-8 16(mod41·17);

и) 21х15 =-2(mod ll ·19);

к)

315х19

=717 (mod 29 · 73).

18.

Для n-го простого числарn, где n = N -5LN/5J+l0, N Е {1, 2, 3,.",

25}, решите сравнение: 1000 · Pn-1 · Pn-2 · x100Pn-3=2Pn-4(mod Pn)·

19.

Разрешимо ли сравнение 7z2 =38(mod 97)?

20.

Найдите остаток от деления:

а)

18 11 19 на 23;

г) 21 2120

на 47;

б)

34333333

на 61;

д) 274830 на 59;

в)

15202215

на 31;

е) 121212

на 17.

25}, найдите остаток от деления

Pn-2

на Pn·

lOOoP•-1

а)

Р2ч1s.47(7);

д) Р2чз3.53(7);

б)

Р2чзч9(ll);

е) P2s.33.s9(125).

в)

Р2чэ.з1(3);

ж) P2s.33.83 (- 7);

г)

P2s.11J.414(3);

з) Р2з.з2.sз(49) .

134

Глава 1. Задачи по курсу теории чисел

27. Найдите длину периода десятичной записи дроби:

а)

1/90241;

д)

1/1035;

и)

5/506;

б)

15/2870;

е)

3/595;

к)

1/41;

в) 7/1044;

ж) 3/1085;

л)

1/37;

r)

9/603;

з)

7/638;

м)

1/41·37.

а)

30

в)

15

g= 7 ;

26 11341 4 ' g= 3;

2211Щ141 '

б)

1

1

79 · 83 g = 24;

r)

61 · 89 g = 56·

29.

165

.

Дайте характеристику двенадцатиричной записи дроби

73. 89. 75

60

30.

Для n-ro простого числа Рп, где n=N-5LN/5J +5, NE{l,2,3, ... ,25},

найдите длину периода g-ичной записи дроби

1000

g =Pn·

PI · Р2 · Pn-3 · Pn-2'

§ 22. Цепные дроби

Цепная дробь [ао, а1, ••• , an, .. .] определяется как формальная сумма

ао +

1

1

,

а1+-...--

..+::

где ао -

некоторое целое число, а все an,

n Е N -

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

причем последнее, если оно существует, отлично от 1.

Рациональные числа Ok=[ao,a1, ••• ,ak]=Pk1Qk, k = 0,1, ... ,n, ... ,

Например,

[-3,2, 1,4] = -3+

1

1

2+--1

1+ -

4

Несложный подсчет показывает, что

[-3

47

'

2 1 4] = --

' '

14.

§ 22. Цепные дроби

135

При этом подходящие дроби имеют вид

до= [-3] = -3,

1

5

д1 = [-3,2] = -3+ 2 = -2,

,

1

8

д2=r-3,2,11 = -3+ -_- 1 = - 3•

2+-

1

/54=(-3,2,1,4]=-3+

1

47

1

= --

2+--1

14

1+4

(обратите внимание на то, что величина [-3, 2, 1]

цеnной дробью не яв­

ляется!); неполные частные имеют вид ао = -3, а1 = 2,

а2 = 1, аз = 4;

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

ao=[-3,2,l,4]=-3+

1

47

=-м·

2+--1

1+4

1

14

а1=[2,1,4] = 2+ -- 1 = s'

1+4

а2 = [1, 4] =

l + 1 =

5

,

а4 =

[4] = 4.

4

4

Свойства цепных дробей

1.

Если дk = Pk/Qk, то Ро = ао, Р1

= а1ао + 1,

и Pn = anPn-1 + Pn-2

для всех n ~ 2.

2.

Если дk = Pk/Qk, то Qo = 1, Q1 = а1, и Qn = anQn-1 + Qn-2 для всех

р + ../l5

a= ---

Q

где Р, Q, D Е Z, D > 1, разлагается в чистопериодическую цепную

дробь тогда и только тогда, когда а > 1 и сопряженная иррациональность

Р- ../l5

Q= ---

Q

лежит в интервале (-1, О).

13.

[ao,a1, ... ,an.···1=

anPn-1 + Pn-2

Q

Q .

an n-1 +

n-2

14.

Если а= [ао, а1, ••• , an•.. .], то

бо < б2 < ... < б2k < ... ~а~ ... < б2н1 < ... < бз < б1.

15.

Если а= [ао, а1, ... , an, .. .], то

la - бnl ~

1

Q Q

n

n+I

Свойства 1 и 2 проверяются непосредственно. Именно, 60 = а0 = а0/1,

то есть 60 = P0/Qo, где Ро = а0, Q0 = 1. Аналогично,

61

= ао + _!_

= аоа1 + I

а1

а1

то есть бо = Po/Qo, где Р1 =

аоа1 + 1, Q1 =

а1. Далее, б2 может быть

получено из 61

заменой величины а1

на величину а1

+ 1/а2, то есть

ао(а1+:J+1

а2(аоа1 + 1) +ао

а2Р1 +Ро

б1 =

1

=

=

а1+­

a1Q1 +Qo'

а2

или, что то же,

б2 = P2/Q2, где Р2 = а2Р1

+ Ро, Q2 = a2Q1 + Qo. Пред­

полагая, ЧТО бn-1 = Pn-1/Qn-I• где

Pn-1

=

an-1Pn-2 + Pn-3. Qn-1 =

(1 -

3VS)

Для разложения числа

2

проведем рассуждения, обобщаю-

щие алгоритм Евклида.

Поскольку 6 < У45 < 7, то для числа

1 -

3VS

равного

1 - У45

,

---

1 - 3VS

2

2

имеет место оценка -3 <

< -2,5, то есть

.

2

ао =

i - 3JSJ = -3.

l

2

Тогда а0 =

1 - 3VS

1

2

= -3 +-,где

а1

..!._ =

1 - зvs - (-3) =

7 -

3VS.

а1

2

2

Следовательно,

а 1 -

2

-

(7 -

2(7 + 3VS)

-

2(7 + 3VS) =

-

7 - зvs -

3VS)(7 + ЗVS) -

49 - 45

2(7 + 3VS)

(7 + 3VS)

4

=

2

Поскольку 6,5 < (7 + 3VS) < 7, то

2

и

а1 =

7 + 3VS

1

2

=6+-,

а2

где ..!._ = 7 + 3VS _

6 =

-5 + ЗVS.

а2

2

2

Следовательно,

2

2(-5-3VS)

2(-5-3VS)

а2 = -5+зvs=(-5+3v'S)(-5-3VS)=

25-45 =

2(5 + 3VS)

(5 + 3VS)

20

=

10

§ 22.

Цепные дроби

139

Поскольку 1,1 < (5 + 3VS)

< 1,2, то

2

а1 = l(5 +1~V5)J= 1,

и

а1=

5 +1~V5 = 1 + ~з,

где -1

= 5 + 3VS -1 = -5 + 3VS .

аз

10

10

Следовательно,

10

10(:-5 -

3VS)

10(-5 - 3VS)

аз= -5 + 3VS = (-5 + 3VS)(-5 - 3VS) =

2545

10(5 + 3VS)

(5 + 3VS)

20

2

Поскольку 5,5 <

(5 + 3VS)

< 6, то

аз = l(5

2

+ ;vs = 5 + ~/

+ ;vs)J= 5,

и

аз =

5

где -1

= 5 + 3VS -5 = -5 + 3VS .

а4

2

2

Таким образом,

а4

а1'

то есть а4 = а2•

Отсюда следует,

что строка,

соответствующая а4,

а4 =

5 + 3VS

=

1

10

1 +-,

as

где

1/а5 = -5 + 3VS

. В частности,

а4

= а2, и

1/а5 =

1/аз, то есть

10

а5

=аз. Продолжая рассуЖДения, получим, что а5=аз и 1/аб= 1/а4,

то

есть а5 = а4; аб

= а4 и 1/а7 = l/as, то

есть а7

= as, и т. д.

Следоиател:~.но,

1- 3VS = [ао, а1, а1, аз, а4, .. .]

= [-3, 6, 1, 5, 1, 5, 1, 5, ...] =

2

= [-3,6,(1,5)].

ложения числа

1 - 3VS

в цепную дробь: начиная с ао =

1 - 3VS

2

2