258

ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ

Доказательство единственности разложения натуральных чисел

на простые множители обычно имеет своим основанием следующее

весьма замечательное предложение, которое оказывается полезным

и во многих других задачах теории чисел.

Т ё оре ма 1. Если натуральные числа а и Ь взаимно прости,

то существуют пшкие целые цисла х и у, что

ах — by 1.

Эту теорему обычно доказывают, опираясь на алгорифм Евклида

и теорию цепных дробей. Мы увидим в главе III, как это может

быть сделано. Здесь же мы приведём другое, методологически

очень поучительное доказательство, данное Гауссом и свободное от

применения каких бы то ни было алгорифмов.

Пусть d есть наименьшее положительное число, которое может

быть представлено в виде

d ах — by

(1)

при надлежащем выборе целых чисел х и у. Мы должны доказать,

что 1; а так как числа а и Ь взаимно просты, т. е. не имеют

других положительных общих делителей, кроме 1, то для этого

достаточно убедиться, что как а, так и Ь делятся на d. В силу

полного равноправия чисел а и Ь достаточно, разумеется, провести

доказательство для какого-нибудь одного из них; мы покажем, что

а делится на d.

Пусть а при делении на d дает в частном т и в остатке г,

так что

Отсюда

а — md а — т (ах — Ьу) а ( 1 — тх) — Ь (— ту) ах' —bY,

где положено:

Таким образом, число может быть представлено в виде

ах'—Ьу' с целыми х', у. Так как r

на и м е нь ш ее положительное число, представимое в форме

ах—Ьу, то число не может быть положительным; следовательно,

и md, т. е. а делится на d, что и требовалось доказать.

Заметим, что мы в сущности доказали теорему, применимую

к любым целым числам а и Ь (не обязательно взаимно простым),

а именно:

Наименьшее положительное число d, представимое в ви-

де ах—Ьу с целыми х и у, есть наибольший общий Делитељ

чисел а и Ь.

В самом деле, что d есть общий делитель чисел а и Ь, нами

уже доказано; но этот общиИ делитель является наибольшим, так