МАЛЫЙ МЕХМАТ МГУ

Кружок 9-11 классов

Теория чисел — 4. Основная теорема арифметики

1.

Найдите а) НОД(1424,320); б) НОД(39210,414).

С помощью алгоритма Евклида можно для чисел n и m найти такие целые числа x и y, что НОД(n,m) = n·x + m·y. (Это странное умение потом несколько раз будет очень полезно.) Для этого достаточно найти НОД(n,m) алгоритмом Евклида, при этом на каждом ходу записывая, как все числа выражаются через n и m.

Пример. Обычный алгоритм Евклида:

2.

Проделайте то же самое для а) НОД(1424,320); б) НОД(39210,414).

3.

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

Пользуясь этим, можно доказать, что если n·m делится на простое число p, то или n делится на p, или m делится на p. Доказательство: допустим, n не делится на p. Тогда НОД(n,p) = 1 (раз p простое). Тогда есть целые x и y такие, что n·x + p·y = 1. Домножим на m: nm·x + pm·y = m. Левая часть делится на p, значит и m делится на p.

Если вам кажется, что это очевидно, и вообще доказывать нечего, то переведите утверждение, которое только что доказывали, на язык яблок: „Было p ящиков яблок, p простое, в каждом ящике одинаковое количество яблок. Из всех яблок выложили прямоугольник. Тогда его можно разделить на p одинаковых прямоугольников или вертикальными разрезами, или горизонтальными (не разрезая яблоки)”.
Мне неизвестны способы доказательства легче, чем приведённый выше. Если вы знаете, то пожалуйста скажите.

4.

Выведите из этого утверждения Основную теорему арифметики: „Каждое натуральное число единственным образом представляется в виде произведения простых”.
Доказать то, что каждое число как-то представляется, просто: надо взять это число и, если оно ещё не простое, разложить его на два множителя. Если какой-то их этих множителй не простой, то его тоже разложить. И так далее. Доказывать то, что представить можно только одним способом, сложнее. Например, можно взять два разложения какого-то числа на простые: p₁ · p₂ · ... · p_n = q₁ · q₂ · ... · q_m и, пользуясь утверждением, доказать, что p₁ = q_k для какого-то k, вывести отсюда, что p₂ · ... · p_n = q₁ · ... · q_{k − 1} · q_{k + 1} · ... · q_m, а дальше поступать аналогично.

5.

Пусть p и q — простые числа. Сколько делителей у числа а) pq; б) p²q²; в) p¹²q¹³?

6.

Найдите наименьшее из таких n, что n! делится на 10¹⁰.

7.

Сколько делителей у числа 50! ?

Hint

Hint. Разложите его на простые множители.

8*.

a, b, c — целые числа. Докажите, что есть такие взаимно простые целые k и l, что ak + bl делится на c.