* Данный текст распознан в автоматическом режиме, поэтому может содержать ошибки

258 ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ Доказательство единственности разложения натуральных чисел на простые множители обычно имеет своим основанием следующее весьма замечательное предложение, которое оказывается полезным и во многих других задачах теории чисел. Т е о р е м а 1. Если натуральные числа а и b взаимно просты, то существуют такие целые числа х и у, что ax~by= I. Эту теорему обычно доказывают, опираясь на алгорифм Евклида и теорию цепных дробей. Мы увидим в главе I I I , как это может быть сделано. Здесь же мы приведём другое, методологически очень поучительное доказательство, данное Гауссом и свободное от применения каких бы то ни было алгорифмов. Пусть d есть наименьшее положительное число, которое может быть представлено в виде d = ax — by (I) при надлежащем выборе целых чисел хну. Мы должны доказать, что d = I ; а так как числа а и b взаимно просты, т. е. не имеют других положительных общих делителей, кроме 1, то для этого достаточно убедиться, что как а, так и b делятся на d. В силу полного равноправия чисел а и Ь достаточно, разумеется, провести доказательство для какого-нибудь одного из них; мы покажем, что а делится на d. Пусть а при делении на d даёт в частном т и в остатке г, так что a=md -J- г (0 ^r<^d). Отсюда r=a — md = a — т(ах — Ьу) = а(\ —тх) — b(—ту) х'= 1 —тх, у = — ту. = cud—ЬУ % где положено: Таким образом, число г может быть представлено в виде ах' — ЬУ с целыми х?, у . Так как r<^d, a d есть по определению наименьшее положительное число, представимое в форме ах — by, то число г не может быть положительным; следовательно, г = 0 и a = md, т. е. а делится на d, что и 1ребовалось доказать. Заметим, что мы в сущности доказали теорему, применимую к любым целым числам а и Ъ (не обязательно взаимно простым), а именно: Наименьшее положительное число d, представимое в ви­ де ах—by с целыми х и у, есть наибольший общий делитель чисел а и Ь. В самом деле, что d есть общий делитель чисел а и Ь, нами уже доказано; но этот общий делитель является наибольшим» так