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

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

Руководители А. С. Воропаев, П. С. Дергач, Ф. И. Мамедова и Ю. А. Цимбалов
2011/2012 учебный год

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

Вспоминаем алгоритм Евклида.
1.
Найдите а) НОД(1424,320); б) НОД(39210,414).

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

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

НОД(511,292) = НОД(219,292) = НОД(219,73) = НОД(146,73) = 73
То же самое, но записываем, как всё выражается из 511 и 292:
НОД(511,292) = НОД(511−292,292) = НОД(511−292,292·2−511).
Получаем, что 292·2 − 511 = 73.

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.
Выведите из этого утверждения Основную теорему арифметики: „Каждое натуральное число единственным образом представляется в виде произведения простых”.
Доказать то, что каждое число как-то представляется, просто: надо взять это число и, если оно ещё не простое, разложить его на два множителя. Если какой-то их этих множителй не простой, то его тоже разложить. И так далее. Доказывать то, что представить можно только одним способом, сложнее. Например, можно взять два разложения какого-то числа на простые: p1 · p2 · ... · pn = q1 · q2 · ... · qm и, пользуясь утверждением, доказать, что p1 = qk для какого-то k, вывести отсюда, что p2 · ... · pn = q1 · ... · qk − 1 · qk + 1 · ... · qm, а дальше поступать аналогично.
5.
Пусть p и q — простые числа. Сколько делителей у числа а) pq; б) p²q²; в) p12q13?
6.
Найдите наименьшее из таких n, что n! делится на 1010.
7.
Сколько делителей у числа 50! ?
Hint. Разложите его на простые множители.
8*.
a, b, c — целые числа. Докажите, что есть такие взаимно простые целые k и l, что ak + bl делится на c.

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS