blog.iakovlev.org
  25.11.2015

Теория чисел

В теории чисел есть множество разнообразных задач, как решенных, так и нет, как очень сложных, так и доступных любому, кто имеет начальный уровень в математике. Их решение зачастую не требует каких-то специальных знаний и навыков, необходим лишь здравый смысл и присутствие логики.
В конце статьи приведен список литературы, которая послужила источником приведенных здесь задач.

Условные обозначения:
НОД = (a, b) - наибольший общий делитель чисел a и b
НОК = [a, b] - наименьшее общее кратное чисел a и b
τ(m) - тау-функция - число делителей числа m
σ(m) - сигма-функция - сумма делителей числа m
φ(n) - фи-функция - равна числу чисел, взаимно простых с n и меньших, чем n
ζ(S) - дзета-функция - сумма ряда величин, обратных натуральным числам.
μ(d) - мю-функция - функция мебиуса

Задачи на делимость

Для любых двух целых чисел a и m существует единственная пара чисел q и r, таких, что a=mq+r. При этом:
a - делимое
m - делитель или модуль
q - частное
r - остаток от деления

Задача Найти число делителей и сумму делителей числа 720.
Решение: Каноническое раpложение числа 720 = 24*32*5
Найдем сумму делителей по формуле: 
      (24+1-1)        (32+1-1)       (51+1-1)      
 S =  ----------- * --------- * ----------------   = 2418
        2 - 1         3 - 1           5 - 1
Найдем число делителей числа 720:
N = (4+1)(2+1)(1+1) = 30

Задача Доказать, что сумма квадратов двух нечетных чисел не является квадратом целого числа.
Доказательство: Нечетное число можно представить в виде 2q1+1. Тогда:
(2q1+1)2 + (2q2+1)2 = 4Q+2., где Q - натуральное число.
Число 4Q+2 - число четное, и очевидно, что при любом Q оно не может быть квадратом, поскольку квадрат четного числа должен делиться на 4, а число вида 4Q+2 не делится на 4.

Задача Доказать, что числа вида 4n + 15n - 1 кратны 9.
Доказательство: 4n + 15n - 1 = (1+3)n + 15n - 1 = 1 + 3n + 9Q + 15n - 1 = 18n + 9Q, где Q - число натуральное

Задача Если сумма двух трехзначных чисел делится на 37, то и шестизначное число, составленное приписыванием одного из них к другому, также делится на 37.
Доказательство: Если N1=abc и N2=def, то abcdef=N1*103 + N2 = (N1 + N2) + 999N1.
(N1 + N2) делится на 37 по определению, а 999 кратно 37.

Задача Вывести общий признак делимости на 7, 11 или 13.
Решение: Известно, что 7*11*13 = 1001. Любое натуральное число можно представить в виде
N = 1000*q + r , где q - число тысяч этого числа, r - остаток при делении этого натурального числа на 1000. Это выражение можно представить в виде:
1000*q + r = (1001 - 1)*q + r = 1001*q + r - q, Очевидно, что в выражении, стоящем справа, первый член суммы делится всегда на 7. 11 и 13.
Также очевидно, что для того, чтобы число N делилось на 7, 11 или 13, необходимо, чтобы оставшаяся часть r - q делилась на 7, 11 или 13. Оставшаяся же часть есть ни что иное, как разница между числом тысяч числа N и остатком деления числа N на тысячу - что и является признаком делимости на 7, 11 или 13.

Задача Даны два разных натуральных числа, имеющих одинаковую сумму цифр. Доказать, что разнось этих чисел кратна 9.
Решение: Каждое число можно представить в виде:
N1 = a1a2a3...an и N2 = b1b2b3...bn. Также
N1 = 9*Q1 + ∑an и N2 = 9*Q2 + ∑bn По условиям задачи, ∑an = ∑bn
Отсюда N1 - N2 = 9(Q1 - Q2)

Задача Найти остаток от деления числа 7402 на 101.
Решение:
101 - простое число. Числа 7 и 101 взаимно просты, поэтому из малой теоремы Ферма следует:
7100 ≡ 1 (mod 101)
Возведем последнее уравнение в четвертую степень:
7400 ≡ 1 (mod 101)
Также:
72 ≡ 49 (mod 101)
Перемножим два последних уравнения:
7402 ≡ 49 (mod 101)
Искомым остатком будет 49.

Задача Найти последние две цифры числа 243402.
Решение:
Достаточно найти остаток от деления 243402 на 100. Очевидно, что:
243402 ≡ 43402 (mod 100)
Поскольку НОД (43, 100) = 1, то используя функцию Эйлера φ(n), где φ(n) - число чисел, взаимно-простых с числом 100:
43φ(100) ≡ 1 (mod 100)
Или
4340 ≡ 1 (mod 100)
Возводим последнее уравнение в 10-ю степень:
43400 ≡ 1 (mod 100)
Известно, что
432 ≡ 49 (mod 100)
Перемножим два последних сравнения
43402 ≡ 49 (mod 100)
Искомый остаток равен 49.

Задача Используя малую теорему Ферма, показать, что 13176 - 1 делится на 89.
Решение:
Используем формулу для разложения разности квадратов
13176 - 1 = (1388 - 1 ) * (1388 + 1 )
89 - число простое. 13 и 89 - взаимно просты. Отсюда по теореме Ферма:
1388 ≡ 1 (mod 89)
Откуда (1388 - 1 ) делится 89, а следовательно, и (13176 - 1 ) делится на 89.


Задачи на нахождение наибольшего общего делителя (НОД) и наименьшего общего кратного [НОК]

Задача Разность двух нечетных чисел равна 2n. Доказать, что эти числа взаимно просты.
Доказательство: У двух нечетных чисел общим делителем может быть только нечетное число. Разность таких двух чисел также должна быть кратна нечетному делителю. А степень двойки может быть кратна нечетному числу только в одном случае - когда этот делитель равен единице.

Задача Найти НОД для следующих чисел:
1. d = (a,b) и m = [a,b]
2. ab и m = [a,b]
3. a+b и m=[a,b]
Решение:
1. (d, m) = (d, [dx, dy]) = d(1, [x, y]) = d
2. (ab, m) = (dm, m)=m(d, 1) = m, где d=(a, b)
3. Пусть (a, b)=d и a = dx, b = dy, где (x, y) = 1. Тогда (a+b, m) = (d(x+y), dxy) = (d(x+y, xy) = d. Следовательно, (а+b, [a, b]) = (a, b).

Задача Решить систему уравнений:
x+y=150
(x,y)=30
Решение:
Второе уравнение равносильно системе из 3 уравнений:
x=30u
y=30v
(u,v)=1
После подстановки в первое уравнение получаем: u+v=5, откуда u может принимать значения 1,2,3,4. Отсюда x=30,60,90,120. y=120,90,60,30.

Задача
Доказать, что произведение НОД на НОК двух чисел равно произведению самих этих чисел
Доказательство:
Обозначим сами числа как a и b, НОД - как d, НОК - как m.
Исходные числа можно выразить через НОД так:
a = A*d , b = B*d, где A и B - два взаимно простых числа, и произведение этих двух чисел, домноженное на НОД, будет кратно каждому из исходных чисел.
Также A*B*d есть ни что иное, как НОК. Отсюда:
m*d = Ad * Bd = a*b



Задачи о простых числах

Задача Разложить на простые множители число 30!
Решение:
Разложение имеет вид:
30! = 2a1 + 3a2 + 5a3 + 7a4 + 11a5 + 13a6 + 17a7 + 19a8 + 23a9 + 29a10
Найдем a1 = |30/2| + |30/4| + |30/8| + |30/16| = 26
Найдем a2 = |30/3| + |30/9| + |30/27| = 14
Найдем a3 = |30/5| + |30/25| = 7
И т.д. В результате
30! = 226 + 314 + 57 + 74 + 112 + 132 + 17 + 19 + 23 + 29

Задача Доказать, что по модулю 4 множество всех простых чисел может быть разбито на два подмножества: на простые числа вида 4п+1 и на простые числа вида 4n+3
Доказательство: Множество всех натуральных чисел по модулю 4 может быть разбито на 4 подмножества (по числу возможных остатков): на числа вида 4п, 4n+1, 4n+2 и 4n+З. Числа вида 4п и вида 4n+2 составные. Следовательно, все простые числа содержатся среди натуральных чисел вида 4n+l и вида 4n+З.

Задача Найти простое число р, чтобы число 2р2+1 было также простым.
Решение: Все простые числа можно разбить на 3 класса: класс простых чисел вида 3q (q=1), класс простых чисел вида 3q+1 (q=2, 4, . . .) и класс простых чисел вида 3q+2 (q=1, 3, . . .). Единственное простое число первого класса p=3 удовлетворяет требованию задачи: 2*9+1 = 19 — число простое. При p=3q+1 или p=3q+2 число 2p2+1 является составным — кратным трем.
Ответ: р=3.

Задача Доказать, что 3, 5 и 7 являются единственной тройкой простых чисел-близнецов (т. е. тройкой простых чисел, составляющих арифметическую прогрессию с разностью 2).
Решение: Рассмотрим числа p, p+2 и p+4 . Положим p=3*q+1(0 = 2, 4, . . .), тогда p+2— число составное (кратное 3). Если p=3q+2 (0=1, 3, . . .), то составным является число p+4.

Задача Доказать, что pn < 22n-1, где pn - простое число (p1=2, p2=3, ...).
Доказательство: p1 = 220. p2 = 3 < 221. Используем тот факт, что простое число всегда меньше произведения всех простых чисел, меньших данного простого числа.
pn+1 < ∏ pn + 1 < 2 * 22 * 222 * ... * 22n-1 + 1 =
22n - 1 + 1 = 22n - 22n - 1 + 1 < 22n

Задача Доказать бесконечность числа простых чисел вида 4m+3.
Решение: Возьмем первые шесть простых чисел вида 4m+3:
m=1, p1=4*1+3=7
m=2, p2=4*2+3=11
m=4, p3=4*4+3=19
m=5, p4=4*5+3=23
m=7, p5=4*7+3=31
m=10, p6=4*10+3=43
Перемножим их, домножим на 4 и отнимем 1:
4*p1*p2*p3*p4*p5*p6 - 1 = 179416467
Полученный результат будет кратен 4*m+3. Почему ?
Отнимем тройку от левой и от правой части:
4*p1*p2*p3*p4*p5*p6 - 1 - 3 = 179416467 - 3
Это эквивалентно выражению:
4*(p1*p2*p3*p4*p5*p6 - 1) = 179416467 - 3
Т.е. число 179416467 при делении на 4 дает в остатке 3:
179416467 ≡ 3 (mod 4)
Т.е число 179416467 делится на число вида 4m+3.
В данном случае результат - 179416467 - канонически разлагается на три простых делителя - 3, 193, 103291. Последнее простое число имеет вид 4*25822+3 - и не совпадает ни с одним исходным простым числом.




Разные задачи

Задача на числа Ферма
Числа вида 2(2n) + 1 называются числами Ферма. Эта последовательность начинается с чисел:
3, 5, 17, 257, 65537, ...
Число Ферма можно вычислить по рекуррентной формуле:
Fn = F0F1...Fn-1 + 2
Доказать, что среди чисел Ферма нет квадратов.
Доказательство:
По определению: Fn = 2(2n) + 1
Отнимем от этого числа единицу и результат возведем в квадрат:
(Fn - 1)2
Покажем, что результат равен следующему числу Ферма, т.е. Fn+1 , за вычетом единицы:
(Fn - 1)2 = (2(2n) + 1 - 1)2 = (2(2n))2 = 2(2n + 1) = Fn+1 - 1
Или - каждое следующее число Ферма равно квадрату разницы между предыдущим числом и единицы:
Fn+1 = (Fn - 1)2
Отсюда : если взять число Ферма Fn, разделить его на 3 и получить в остатке 2:
Fn ≡ 2 (mod 3)
то следующее число Ферма будет обладать тем же самым свойством:
Fn+1 ≡ 2 (mod 3)
Берем второе число Ферма:
F1 = 5 ≡ 2 (mod 3)
Значит, все остальные числа Ферма обладают ровно таким же свойством.
А если число при делении на 3 дает в остатке 2, оно не может быть квадратом.

Задача на числа Ферма
Вычислить, из скольки разрядов состоит 73-е по счету число Ферма, а также его последние три цифры
Решение:
Два в десятой степени состоит из 4-х цифр - это чуть больше 10 в третьей - :
210 = 1024 > 103
Два в 73 степени - это восемь умножить на два в 70-й. Очевидно, что два в 70-й состоит из числа цифр, в 7 раз большее, чем два в десятой:
273 = 8 * 270 > 8 * 1021
Используя эти данные, найдем, из скольки цифр состоит 73-е число Ферма:
2(273) = 28*1021 = (280)1020 = ((210)8)1020 > 1024*1020
Т.о. 73-е число Ферма состоит более чем из 24*1020 цифр.
Для нахождения последних трех цифр будем использовать тот факт, что квадрат любого натурального числа и его 22-я степень всегда имеют одни и те же последние две цифры:
n22 = n2(mod 100)
А также тот факт, что куб числа и его 103-я степень всегда имеют одни и те же последние 3 цифры:
n103 = n3(mod 1000)
Используя первое свойство, для любого k имеем:
nk+22 = nk * n22 ≡ nk * n2 = nk+2
что означает: если показатель степени больше 22, из него можно спокойно вычитать 20 до тех пор, пока степень не станет равной или больше двух.
Аналогично, испоьзуя второе свойство, можно вычитать 100 до тех пор, пока степень не станет равной или больше трех. Т.о.:
273 = 260+13 = 213(mod 100)
Теперь можно найти две последние цифры двойки в 73-й степени:
273 = 213 = 23 * 210 = 8*1024 ≡ 8 * 24 = 192 ≡ 92
Или:
273 = 100*q + 92
Тогда
2(273) = 2100*q + 92 ≡ 292 (mod 1000)
Далее просто возводим два в 92-ю степень - последние три цифры этого числа есть 896.
Прибавляем 1: искомые последние три цифры 73-го числа Ферма - 897.


Задача Что больше - eπ или πe ?
Решение: Показательную функцию можно разложить в ряд:
ex = 1 + x + x2 ⁄ 2 + ...
Сумма этого ряда будет больше, чем 1+x
Поскольку π > e, или π/e > 1, или π/e - 1 > 0
Принимаем x = π/e - 1
Тогда
eπ/e - 1 > 1 + (π/e - 1) , или eπ/e / e > π/e
Левую и правую части последнего уравнения умножаем на e:
eπ/e > π
Левую и правую части последнего уравнения возводим в степень e:
eπ > πe

Задача
Доказать, что произведение 8 последовательных натуральных чисел никогда не может быть четвертой степенью целого числа.
Доказательство:
Такое произведение можно записать в виде:
P = x(x+7) * (x+1)(x+6) * (x+2)(x+5) * (x+3)(x+4) = (x2+7x) * (x2+7x+6) * (x2+7x+10) * (x2+7x+12)
Введем новую переменную: a = x2+7x+6
P = (a-6) * a * (a+4) * (a+6) = (a2 - 36)(a2 + 4a) = а4 + 4а3 — З6a2 — 144а = а4 + 4а(a2 — 9а — 36) = а4 + 4а(a + 3) (а — 12)
Получили сумму 2 чисел - одно из них является четвертой степенью, т.е.
P > a4
Четвертая степень следующего за a числа
(a+1)4 = a4 + 4a3 + 6a2 + 4a + 1
Очевидно, что
P < (a+1)4
Т.е. P находится между двумя последовательными четвертыми степенями.


Задача Дано целое число A, у которого есть взаимно-простые с ним числа n. Также у этого числа A имеются простые делители p. Убедиться в справедливости следующего равенства:

∑ 1 ⁄ nS = ζ(S) * ∏ (1 - 1 ⁄ pS)

Здесь в левой части - ряд чисел n, взаимно-простых с A, в правой части - произведение дзета-функции на произведение делителей числа A. S > 1.
Например, пусть A = 24. Тогда n = 1,5,7,11,13,17,19,23. p=2,3.
Пусть S = 2. ζ(2) = 1.644934066848
В левой части равенства имеем:
1+1/52+1/72+1/112+1/132+1/172+1/192+1/232=1.08...
В правой части : 1.644934066848 * ((1-1/2S)*(1-1/3S)) = 1.08...
Для строгого доказательства можно вычислить производную от функции 1/xS.
Следующий код иллюстрирует данную задачу:
Код


Задача Имеется произвольный ряд натуральных чисел: 1,2,3,4,5. Пусть имеется произвольное число a=10. Пусть d - все делители числа a. Обозначим через S сумму чисел из ряда, взаимно простых с a. Тогда:

S = ∑ μ(d)*Sd

В правой части ряд пробегает по всем значениям d. μ(d) - функция Мебиуса, Sd - сумма значений из исходного ряда, кратных d.
В нашем примере S = 1+3=4. d=[1,2,5]. В правой части будет сумма ряда:
μ(1)*(1+2+3+4+5) + μ(2)*(2+4) + μ(5)*(5) = 1*15 -1*6 -1*5 = 15 - 6 - 5 = 4
4=4
что и требовалось получить. Следующий код иллюстрирует данную задачу:
Код


Задача Функция φ(n) равна числу чисел, взаимно простых с n и меньших, чем n. Функцию ввел в обиход Эйлер. Показать справедливость равенства при n -> ∞:

∑ φ(n) ⁄ nS = ζ(S-1) ⁄ ζ(S)


Ряд значений слева равен отношению двух значений дзета-функции справа. Доказывается это следующим образом:

Пусть S=3. Тогда справа имеем 1.36843277762. При вычислении ряда слева при n=2000 получаем точность до 3-го знака после запятой:1.368128805559588544001282384. Следующий код иллюстрирует задачу:
Код

Виноградов. Основы теории чисел

Серпинский. 250 задач по элементарной теории чисел

 Автор   Комментарий к данному блогу
Комментарий

Ваше имя:
Комментарий:
Оба поля являются обязательными