Deza_Kotova_Sbornik_zadach_po_teorii_chisel

Таким образом, 1315/406 = {3, 4, 5, 2, 1, 1, 3].

Найдем подходящую дробь с нечетным индексом, обладающую наи­ большим знаменателем, не превосходящим 100. Для этого исполь­ зуем стандартную таблицу, заполняя в ней сначала только строку, соответствующую знаменателям подходящих дробей. Остановившись

на первом элементе строки, большем ста, мы получим табл.16. Таким образом, наилучшим приближением числа 1315/406 дробью а/Ь со знаменателем, не превосходящим 100, будет подходящая дробь 64 • Однако данное приближение является приближением с недостат­

ком в силу четности индекса 4. Поэтому наилучшим приближением

числа 1315/406 с избытком дробью а/Ь со знаменателем, не превосхо­ дящим 100, будет предыдущая подходящая дробь 63 = P3/Q3 • Работа

по вычислению Рз приводит к табл.17.

Таким образом, искомое приближение числа -v15 имеет вид -v15:::::::

3. Сократите дробь -667/580.

Реwение. Разложим чнсло 667/580 в цепную дробь:

667 = 580 . 1 + 87;

580 = 87 . 6 + 58;

87 = 58. 1 + 29;

58 = 29. 2 +о.

Таким образом, 667/580 = {1, 6, 1, 2].

Найдем значение цепной дроби {1, 6, 1, 2], используя стандартную таблицу (табл. 18).

Таким образом, 667/580 = 23/20, и -667/580 = -23/20, причем дробь

Решение. Перейдя к сравнению 41х = 19(mod 114), получим разло­

жение дроби 38/41 в цепную дробь:

114 = 41. 3 + 21;

41 = 21 . 1 + 20; 21=20.1+1; 20 = 1·20 +о.

Таким образом, 114/41=(3,1, 1, 20}.

Найдем числители и знаменатели подходящих к цепной дроби [3, 1, 1, 20]

дробей, используя стандартную таблицу (табл. 19).

Таким образом, х = (-7) · 19 = -133=-19(mod114). Разбивая один

класс по модулю 114 на три класса по модулю 342, мы получим окон­

чательный результат: решениями сравнения 123х = 57(mod 342) явля­

ются классы x:=-19(mod342), x:=95(mod342) и x:=223(mod342). !>

5.Решите неопределенное уравнение 33х + 51у = 21.

Решение. Приведя уравнение к виду l lx + 17у = 7, разложим число 17/11 в цепную дробь:

Таким образом, первые четыре натуральных решения уравнения х2 -

найдены по формулам х = P2n-1 , у = Q2n- I , где n Е N, причем

1. Найдитерациональное приближение числа v'IO с точностью д= 5· 10-3 .

Укажите, с избытком или с недостатком полученное приближение.

2.Найдите рациональное приближение числа J2l с недостатком с точ­

ностью д = 10-4 •

3.Найдите величину бесконечной цепной дроби [-2, (1, 1, 2)] и ее ра­ циональное приближение с недостатком (с избытком) с точностью

д = 10-2 •

4.Найдите наилучшее приближение числа 2500/1441 дробью а/Ь со зна­

менателем, не превосходящим 100. Укажите, с избытком или с недо­

статком полученное приближение.

5.Найдите наилучшее приближение числа 1292/479 с избытком (с не­

достатком) дробью а/Ь со знаменателем, не превосходящим 100. Ука­

жите точность приближения. 6. Сократите дробь:

•наилучшим приближением этого числа со знаменателем, не пре­

восходящим 7;

•наилучшим приближением этого числа со знаменателем, не пре­ восходящим 8?

8.Найдите подходящую дробь наименьшего порядка, приближающую

число 61/44 с точностью 1/50. Является ли она:

•наилучшим приближением этого числа со знаменателем, не пре­ восходящим 5;

•наилучшим приближением этого числа со знаменателем, не пре­ восходящим 6?

9.Найдите подходящую дробь наименьшего порядка, приближающую

число 37/64 с точностью 10-2• Является ли она:

•наилучшим приближением этого числа со знаменателем, не пре­ восходящим 7;

•наилучшим приближением этого числа со знаменателем, не пре­ восходящим 8?

10.Для n = N -4LN/4J +5, где N Е {1, 2, 3, ... , 25}, разложите в цепную

дробь число

362n

905 • 2n ·

Найдите наилучшее приближение указанного числа обыкновенной дробью с знаменателем, не превосходящим 20n. С избытком или

с недостатком полученное приближение?

11.Для n = N -4LN/4J +5, где N Е {1, 2, 3, ... , 25}, разложите в цепную

дробь число

V37n-2n

2

и найдите его рациональное приближение с точностью 10-4 •

12.Найдите рациональное приближение числа а с точностью д, если

io-6 , io-1}.

13. Найдите рациональное приближение числа а с точностью д, если:

21.Для n = N -4LN/4j + 5, где N Е {1, 2, 3, ... , 25}, решите уравнение

221х - 39ny = 182.

22.Укажите, если это возможно, первые два натуральных решения урав-

нения:

§ 24. Разные теоретико-чисnовь1е задачи

1.Найдите все пары натуральных чисел, таких что при делении на 41

их сумма дает остаток 6, а сумма их квадратов дает остаток 20.

2.Два двузначных числа отличаются друг от друга только порядком

цифр. Их разность при делении на 11 дает в остатке 1. Найдите эти

числа.

3. Найдите наименьшее натуральное трехзначное число, кратное 23,

укоторого каждая следующая цифра больше предьщущей на единицу.

4.Найдите все натуральные трехзначные числа, которые при делении на 41 дают остаток, равный сумме своих цифр.

5.Найдите два наименьших положительных соседних нечетных числа, произведение которых делится на 187.

6.Разделите многочлен /(х) на многочлен g(x) с остатком, считая, что

коэффициенты многочленов принадлежат Z (Z/2Z, Z/3Z, Z/5Z):

а) /(х) = 2х5 + х4 +4х + 3, g(x) = 3х2 + 1;

б) f(:c)=x6 -x+l,g(x)=x-1;

7. Найдите многочлен r(x), если /(х) =: r(x) (mod g(x)), degr(x) <

< degg(x), и коэффициенты многочленов принадлежат Z (Z/2Z,

Z/ЗZ, Z/5Z):

а) /(х) = ж3 + х2 + 2х + 2, g(x) = х2 + 1;

б) f(x) = 8х8 + 6:с6 + 4:с4 + 2х2 , g(x) = бх + 3; в) /(:с)= :с20 + х10 + 1, g(x) = :с5 + 1.

10. Сколько существует упорядоченных пар натуральных чисел а и Ь,

для которых (а, Ь) = 6 и [а, Ь] = 6930? Сформулируйте ответ в общем

случае, используя канонические разложения (а, Ь) и [а, Ь].

11. Докажите, что десятичная запись квадрата натурального числа не мо­

жет состоять из одинаковых цифр.

12.Докажите, что для любого натурального числа n существует кратное

ему натуральное число m, которое в десятичной системе счисления записывается только цифрами О и 1.

13.Разложите на простые множители число 222 + 39 · 210 + 81.

дится.

16.Найдите всех, для которых LxJ = 5, а {х} = 0.3.

17.Делится ли.10! на т(3)15 ?

18.Найдите остаток от деления числа т(275)и(ш)~(2,s) на т(12!).

19.Приведите пример кольца классов вычетов, в котором верно соотно-

шение:

20. Для каких модулей можно составить приведенную систему вычетов, состоящую из степеней ч.исла 3?

21. Докажите, что произведение всех натуральных чисел, меньших р2

r){ 3х +4у- 29=O(mod143). 2х - 5у + 84 = O(mod 143) '

29.Делится ли на 10932 число 21093 - 2?

30.Решите сравнение 3х2 = IO(mod 172).

3х2 + 5х - 5 ::: O(mod 17)

{2х =10(mod40)

32.Найдите четыре наименьших положительных последовательных не­

четных числа, которые делятся на 7, 11, 13 и 17, соответственно.

33.Припишите к числу 12 345 еще пять цифр так, чтобы получилось число, делящееся на 41.

34.Припишите к числу 1234567890 еще пятьдесят цифр так, чтобы по­ лучилось число, делящееся на 31.Решите систему сравнений