Deza_Kotova_Sbornik_zadach_po_teorii_chisel

просты.

б. Докажите, что два различных простых числа р и q взаимно просты:

(р, q) = 1, если р, q Е 1Р', р =F q.

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

различных простых чисел р и q: (pn, qm) = 1, если р, q Е JP>, р =F q,

n,mENU{O}.

задачu

1.Докажите, что если (а, Ь) = 1, то (ас, Ь) = (Ь, с), где а, Ь, с Е Z.

2.Докажите, что (а, Ь) =(а+ Ь, [а, Ь]), где а, Ь Е Z.

3.Найдите натуральные числа а и Ь, такие, что:

8.Докажите, что при любых целых а и Ь число аЬ(а4 - Ь4) делится на 30.

9.Докажите, что число 7а3/3 + 3а2/2 + а/6 является целым при любом

натуральном а.

10.Докажите, что (n7 - n3 + 1, 30) = 1 при любом натуральном n.

11.Докажите, что из равенства несократимых дробей следует равенство

их числителей и знаменателей.

12. Пусть m, n, а Е N, причем (m, n) = 1. Докажите, что если dl(am - 1)

иdlan - 1, то dl(at - 1) при любом натуральном t.

§7. Функции LжJ и {ж}

В теории чисел рассматриваются разнообразные функции, значения которых для натурального аргумента n связаны с арифметической при­ родой числа n. Множество таких функций обычно ограничивают только одним требованием: каждая функция должна быть определена для всех на­ туральных значений аргумента. Таким образом, комплекснозначная функ­

ция /(n) называется арифметической функцией (или числовой функцией), если значение /(n) определено для любого натурального числа n. Обычно

в теории чисел рассматриваются либо функции, которые вообще опреде­ лены только при натуральных значениях аргумента, либо функции, для

которых натуральные (целые) значения аргумента являются характеристи­

ческцми точками, определяющими величину функции и в других точках. Известными арифметическими функциями являются функции целая

часть числа и дробная часть числа.

Функция целая часть х, обозначаемая lхJ, есть наибольшее целое число, не превосходящее х. Например, L2.9J =2, l-2J = -2, и L-2.3J = -3.

Функция дробная часть х, обозначаемая {х}, определяется как {х} =

= х - LxJ. Например, {2.9} = 0.9, {-2} =О, и {-2.3} = 0.7.

Часто используется и функция llxll = min{{x}, l - {х}}, дающая

расстояние от х до ближайшего целого числа. Например, 112.911 = 0.1,

11 - 211 =о, и 11- 2.311 = о.3.

Менее известнафункция Гхl •определяемая как наименьшее целое чис­

ло, большее или равное х. Например, Г2,9l = 3, Г-21 = -2, и Г-2,31 = -2.

и только если n ~ LxJ.

/(х)

2 --

-2 -1 о 1 2

-1

-- 2

Рис. 1. /(х) = lxJ

f(x)

Рис.2. /(х) = {х}

4. j{n Е N : n ~ х, djn}J = Lx/dj для любого положительного действи­

тельного числа х и любого натурального числа d.

5.LLxJJ = LxJ для любого действительного числах.

6.Lx/dJ = LLxJ/dJ для любогоположительного действительного числах

илюбого натурального числа d.

7. LxJ - 2Lx/2J =О или 1 для любого действительного числах.

8.n! = р~' · ... · p~k, где Pi пробегает все простые числа, не превосходя­

щие n, и O:i = Ln/piJ + Ln/p;J + Ln/pfj + " ..

9.О ~ {х} < 1 для любого действительного числа х с равенством слева,

если и :голько если х - целое число.

10. {k + х} = {х} для любого целого числа k и любого действительного

числах.

Например, для доказательства формулы J{n Е N: n ~ х, djn}I = Lx/dJ достаточно рассмотреть числа d, 2d, ... , kd ~ х < (k+ I)d. Тогда l{n Е N:

Поскольку функция f (х) = lхJ обладает свойством lх + kJ = lхJ + k для любого целого числа k, и для х Е [О, 1) имеет место равенство lхJ = О, то для х Е [1, 2) имеет место равенство lхJ = 1, для х Е (2, 3) имеет место равенство lxJ = 2, ... , для х Е (-1, О) имеет место равенство lxJ = -1,

для х Е (-2, -1) имеет место равенство lxJ = -2, и график функции

/(х) = lxJ изображен на рис. 1.

Поскольку функция /(х) = {х} является периодической с периодом 1, и для х Е (О, 1) имеет место равенство {х} = х, то график функции

/(х) = {х} изображен на рис. 2.

nрuмеры решен,.,u...я задач_

1. Сколько натуральных n, не превосходящих 1000, не делится ни на 5,

= 1000-ll000/5J-ll000/7J+ ll000/35J = 1000-200-142+28 = 686. r>

2.Запишите каноническое разложение числа 20!.

Решение. Для нахождения данного разложения мы выписываем все

простые числа р, не превосхдящие 20, то есть числа 2, 3, 5, 7, 11, 13, 17 и 19. Для каждого такого р степень а, в которой р входит в разложение

факториала, вычисляем по формуле a=l20/pJ+l20/p2J+l20/p3J+ ...

При этом поскольку l20/pkJ = l20/pk-IjpJ = ll20/pk-IJ/pJ, то вы­

числения упрощаются: на каждом следующем шаге мы делим на р

предьщущее слагаемое и выписываем целую часть полученного чис­

ла. Именно, для числа 2 вычисления принимают вид а1 = l20/2J +

+ l20/22J + l20/23J + l20/24J + l20/25J + ... = 10+ ll0/2J + lll0/2J/2J +

... = 10 + 5 + 2 + 1 +О = 18. Для числа 3 вычисления принимают

вид а1 = L20/3J + l20/32J + l20/33J + ... = 6 + 2 +О= 8. Для числа 5 имеем аз = l20/5J + l20/52J + ... = 4 +О= 4. Для числа 7 имеем а4 = l20/7J + l20/72J + ... = 2 +О = 2. Поскольку для числа 11

результат принимает вид а5 = l20/l1J + l20/11 2J + ... = 1+О=1, то

дальнейшие вычисления не требуются - оставшиеся простые числа

13, 17 и 19 также будут входить в разложение числа 20! в первой

степени. Таким образом, 20! = 218 • 38 • 54 • 72 • 11·13 · 17 · 19. r>

3.Сколькими нулями оканчивается число 2000! в пятнадцатиричной

системе счисления?

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

(хн1, /(хн1)), (хн1. /(xi)) значения функции /(х) располага­ ются между величинами /i и /н1, то есть l/(x)J = min{/i, /i+1};

•для построения графика функции у= {/(х)} поднять (или опу­ стить) часть графика функции у = /(х), находящуюся в том

или ином прямоугольнике построенной сетки, на ось абсцисс:

внутри прямоугольника с вершинами (xi, /(xi)), (х;, /(хн1)),

(хн1. /(хн1)), (хн1, /(xi)) значения функции /(х) располага­ ются между величинами /i и /н1. то есть {/(х)} = /(х) -

min{/i, /i+1}.

На рис. 3 показана сетка, построенная для графика функции /(х) =

1.Сколько натуральных чисел, не превосходящих 200, не делится ни на 2, ни на 5?

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

ни на 3, ни на 11?

3.Сколько двузначных натуральных чисел не делится ни на 3, ни на 11?

4.Сколько натуральных чисел, не превосходящих 100, не делится ни на 2, ни на 3, ни на 5?

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

ни на 5, ни на 7, ни на 11?

б. Сколько существует натуральных чисел, не превосходящих 300 и вза­

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

7.Сколько существует натуральных чисел, не превосходящих 100 и вза­ имно простых с 36?

8.Сколько существует натуральных чисел, не превосходящих 300 и вза~ имно простых с 300?

9.Сколько существует трехзначных натуральных чисел, взаимно про­

стых с 1000?

10.Запишите каноническое разложение чисел:

12.Постройте графики функций /(х) = llxl! и.. /(х) = Гхl.

13.Докажите:

и) E,Lnp/qJ+ f,lmq/pj =---(q-1)/2, где m,nEN, p,qEP\{2}, 2

pf.q.

14. Докажите, что

~(l:J -ln:1J) = 2 ~n ЕР.

15.Докажите, что для действительного нецелого х имеет место следующее разложение в ряд Фурье:

17.Докажите, что для непрерывной функции /(х), неотрицательной

на отрезке [а, Ь], число точек (х, у) с натуральными координата­

ми х, у в криволинейной трапеции, ограниченной линиями х = а,