Таблицы Брадиса

Утверждение этой задачи существенно облегчает

Утверждение этой задачи существенно облегчает

Элементы математики в задачах - Г. А. Мерзон

Решение. В одну сторону утверждение очевидно (а — составное, если а делится на какое-нибудь простое число, не превосходящее </а).

Докажем другую часть утверждения. Пусть а составное. Это зна­чит, что найдутся два целых числа т и п таких, что а = тп, т > 1, п > 1. Если предположить, что т > */а, п > 4а, то перемножая эти неравенства, получим, что тп > а. Противоречие.

& Утверждение этой задачи существенно облегчает проверку про­стоты числа. Действительно, для того чтобы число было простым необходимо и достаточно, чтобы оно не делилось ни на одно про­стое, не превосходящее корень из данного числа, а таких простых сравнительно немного.

Задача 16. Докажите, что:

а) любое целое число, большее 1, можно представить в виде про­изведения простых чисел;

б) каждое целое число х, большее 1, можно представить в виде

аі йо а

х = Р1 Р22- • Р" >

где р1 < р2 < .•. < рп —простые числа, а1, а2, • •., ап —положительные целые числа;

в*) (Основная теорема арифметики) если число х представлено двумя способами в таком виде, а точнее

а а? а,          Ъл Ъ2 Ъ^

х = р/р2 ...рпп = 4142...чтт> то эти разложения совпадают, то есть т = п и при любом 1 ^ і ^ п рі = Чі, аі =

г)     если в этом разложении все аі четны, то х есть точный квадрат, то есть найдется такое целое у, что х = у2.

Решение. а) Любое целое число, большее 1, если оно не является простым, раскладывается (возможно, не единственным способом) в произведение двух чисел, больших единицы. Каждое из них либо является простым, либо также в свою очередь раскладывается в про­изведение. Так как на каждом шаге у нас числа уменьшаются, то ясно, что процесс разложения рано или поздно закончится и мы получим разложение на простые.