VI.4. Арифметика и теория чисел

Все числа в этом разделе являются целыми. Напомним, что число называется простым, если оно не имеет делителей, отличных от 1 и самого числа ; число , не являющееся простым, называется составным (такое число кратно некоторому числу , ); число 1 не относится ни к простым, ни к составным.

77. (Поиск арифметических тождеств.) Найти несколько четверок натуральных чисел a, b, d, c, для которых .

Замечание. Массивы здесь не нужны!

78. (Числа Армстронга.) Число n, записанное в десятичной системе счисления как последовательность цифр , где , называется числом Армстронга, если , где b_i – числовое значение цифры a_i. Например, и – числа Армстронга.

1. Найти все числа Армстронга .

2. Построить вектор , где z_k равно числу всех чисел Армстронга, содержащих цифр.

3. Обобщить задачу для p-ичных чисел,

79. (Простые и составные числа. Числа, взаимно простые с заданным числом n.) Пусть p_k обозначает k-ое простое число, q_l – l-ое составное число, а – m-ое натуральное число, взаимно простое с n. (Таким образом, p₁=2, p₂=3, p₃=5, p₄=7, p₅=11,…; q₁=4, q₂=6, q₃=8, q₄=9,…; если , то )

Для заданных s и n построить множества (массивы) , , .

80. (Основная теорема арифметики.) Любое натуральное число однозначно представимо в виде

, (_*)

где – простые числа; – натуральные числа.

1. Вычислить наименьший и наибольший простые делители числа n; вычислить наибольший делитель числа n, не делящийся на квадрат простого числа. (Эти делители суть ).

2. Получить разложение (_*).

Замечание. О разложении чисел на простые множители см., например, книгу Д.Кнута "Искусство программирования для ЭВМ", том 2: Получисленные алгоритмы. – М.Мир, 1977, § 4.5.4, сс. 409-436. В настоящее время нет достаточно эффективных алгоритмов решения этой задачи.

81. (Длинные интервалы составных чисел.) Найти наименьшее , для которого последовательность целых чисел заданной длины k не содержит простых чисел.

82. (Простые числа близнецы.) Простые числа и называются близнецами, если . Перенумеруем пары простых чисел-близнецов в порядке возрастания наименьшего числа в паре. Построить вектор

,

где – n-ая пара простых чисел-близнецов.

83. (Простые числа в арифметической прогрессии.) Для заданных взаимно простых чисел и , , построить вектор , где – -ое (по порядку) простое число в арифметической прогрессии ,

Замечание. Если целые числа a и взаимно просты (т.е. не имеют общего делителя, отличного от 1), то согласно известной теореме Дирихле в арифметической прогрессии содержится бесконечное число простых чисел.

84. (Задача Дж. Вейзенбаума.) Для заданного натурального вычислить наименьшее число , представимое в виде , где – натуральные числа, причем и . (Пример: для имеем .

Замечание: массивы здесь не нужны!)

85. (Закрепление пройденного, или две вариации на тему задачи 84.)

1. Для заданных натуральных и вычислить наименьшее число , представимое в виде , где – натуральные числа, , причем, если , то и . Построить таблицу чисел для s, t=1,2,…,5.

2. Вычислить 10 наименьших чисел , представимых в виде , где – натуральные числа, причем , , .

86. (Пример развития темы.)

1. Найти все четверки натуральных чисел l, i, j, k для которых и .

2. Вычислить 10 натуральных чисел , куб которых есть сумма кубов трех натуральных чисел, т.е.

, . (_*)

При этом число должно быть наименьшим, для которого возможно такое представление. Если уже получены такие числа , то очередное число должно быть наименьшим числом, для которого возможно представление (_*) и которое взаимно просто с каждым из чисел .

87. (Представление чисел суммами k-ых степеней.)

1. Для заданных натуральных чисел k и m построить вектор , где z_n – число решений уравнения в целых числах , .

2. Для заданных натуральных чисел k, l и m построить вектор , где z_n – число решений уравнения в целых числах ,

88. (Теорема Лагранжа о четырех квадратах.) Известно, что любое натуральное число есть сумма не более чем четырех квадратов, т.е. , где – целые числа. Построить векторы , s=1,2,3,4, где z_sn – число решений уравнения в натуральных числах .

89. (Многоугольные числа.) k-ое m-угольное число задается формулой

, ;

Пьер Ферма высказал, а Огюст Коши доказал, что каждое натуральное число n есть сумма не более m m-угольных чисел.

1. Проверить это утверждение для и .

2. Построить векторы , где – число решений уравнения в m-угольных числах , ; .

90. (Проблема Варинга.) Давид Гилберт первым доказал следующее утверждение: для целого числа существует число такое, что любое число n представимо в виде

,

где . Все числа здесь целые и неотрицательны. Предполагают, что , где – целая часть .

1. Проверить для чисел , что .

2. Построить векторы , где равно наименьшему s, при котором уравнение разрешимо в целых числах . (Очевидно, что . Известно, что , .)

91. (Проблема Варинга для кольца целых чисел по модулю m.)

1. Для заданных и найти наименьшее , обладающее следующим свойством: для любого найдутся такие, что . (Заведомо .)

2. Построить таблицу чисел для .

38