Книги по разным темам Pages:     | 1 |   ...   | 8 | 9 | 10 | 11 | 12 |   ...   | 76 |

p-Тогда a xp-1, и согласно теореме Ферма правая, а следовательно, и левая части сравнения должны быть сравнимы с 1 по модулю p. Такое число a (не являющееся кратным p), которое по модулю p сравнимо с квадратом некоторого числа, называется квадратическим вычетом p;

напротив, число b, не кратное p, которое не сравнимо ни с каким квадратом по модулю p, называется квадратическим невычетом p. Мы только 64 ТЕОРИЯ ЧИСЕЛ гл. I что видели, что всякий квадратический вычет a числа p удовлетворяет p-сравнению a 1 (mod p). Довольно легко установить, что всякий p-невычет b числа p удовлетворяет сравнению b -1 (mod p). Кроме того, мы покажем (несколько дальше), что среди чисел 1, 2, 3,..., p - p - 1 p - имеется в точности квадратических вычетов и невычетов.

2 Хотя с помощью прямых подсчетов можно было собрать немало эмпирических данных, но открыть сразу общие законы, регулирующие распределение квадратических вычетов, было нелегко. Первое глубоко лежащее свойство этих вычетов было подмечено Лежандром (1752 - 1833); позднее Гаусс назвал его законом взаимности. Этот закон касается взаимоотношения между двумя различными простыми числами p и q. Он заключается в следующем:

p - 1 q - 1) Предположим, что произведение четное. Тогда q есть 2 вычет p в том и только том случае, если p есть вычет q.

2) Предположим, напротив, что указанное произведение Ч нечетное.

Тогда ситуация резко меняется: q есть вычет p, если p есть невычет q, и наоборот.

Первое строгое доказательство закона взаимности, долгое время остававшегося гипотезой, данное Гауссом еще в молодости, явилось одним из крупных его достижений. Доказательство Гаусса никоим образом нельзя назвать простым, и в наше время провести доказательство закона взаимности стоит известного труда, хотя количество различных опубликованных доказательств очень велико. Истинный смысл закона взаимности вскрылся лишь в недавнее время Ч в связи с новейшим развитием алгебраической теории чисел.

В качестве примера, иллюстрирующего распределение квадратических вычетов, возьмем p = 7. Так как по модулю 02 0, 12 1, 22 4, 32 2, 42 2, 52 4, 62 и так как дальнейшие квадраты повторяют эту последовательность, то квадратическими вычетами числа 7 являются числа, сравнимые с 1, и 4, а невычетами Ч числа, сравнимые с 3, 5 и 6. В общем случае квадратические вычеты p составляются из чисел, сравнимых с числами 12, 22,..., (p - 1)2. Но эти последние попарно сравнимы, так как x2 (p - x)2 (mod p) (например, 22 52 (mod 7)).

Действительно, (p - x)2 = p2 - 2px + x2 x2 (mod p). Значит, половина чисел 1, 2,..., p - 1 представляет собою квадратические вычеты числа p, а другая половина Ч невычеты.

Чтобы дать иллюстрацию также и закону взаимности, положим p = 5, q = 11. Так как 11 12 (mod 5), то 11 есть квадратический 5 - 1 11 - вычет по модулю 5, и так как, кроме того, произведение 2 з 3 ПИФАГОРОВЫ ЧИСЛА И БОЛЬШАЯ ТЕОРЕМА ФЕРМА четное, то согласно закону взаимности 5 должно быть также квадратическим вычетом по модулю 11; и в самом деле, мы видим, что 5 42 (mod 11). С другой стороны, положим p = 7, q = 11. Тогда 7 - 1 11 - произведение нечетно, и в этом случае 11 есть вычет 2 по модулю 7 (так как 11 22 (mod 7)), а 7 Ч невычет по модулю 11.

Упражнения. 1) 62 = 36 13 (mod 23). Является ли 23 квадратическим вычетом по модулю 13 2) Мы видели, что x2 (p - x)2 (mod p). Покажите, что иного вида сравнений между числами 12, 22, 32,..., (p - 1)2 быть не может.

з 3. Пифагоровы числа и большая теорема Ферма Интересный вопрос из области теории чисел связан с теоремой Пифагора. Теорема эта, как известно, алгебраически выражается равенством a2 + b2 = c2, (1) где a и b Ч длины катетов, а c Ч длина гипотенузы. Проблема разыскания всех прямоугольных треугольников, стороны которых выражаются целыми числами, таким образом, эквивалентна проблеме нахождения всех решений (a, b, c) в целых числах уравнения (1). Каждая тройка целых чисел (a, b, c), удовлетворяющих этому уравнению, носит название пифагоровой тройки.

Все пифагоровы тройки могут быть найдены довольно просто. Пусть целые числа a, b и c образуют пифагорову тройку, т. е. связаны соотноa b шением a2 + b2 = c2. Положим ради краткости = x, = y. Тогда x c c и y Ч рациональные числа, связанные равенством x2 + y2 = 1. Из поy 1 - x следнего следует: y2 = (1 - x)(1 + x) или =. Общее значение 1 + x y двух отношений в полученной пропорции есть число t, которое может u быть представлено как отношение двух целых чисел. Можно, далее, v написать: y = t(1 + x) и (1 - x) = ty, или же tx - y = -t, x + ty = 1.

Из полученной системы уравнений немедленно следует, что 1 - t2 2t x =, y =.

1 + t2 1 + ta b u Подставляя и вместо x и y и вместо t, будем иметь c c v a v2 - u2 b 2uv =, =.

c u2 + v2 c u2 + v Отсюда вытекает a = (v2 - u2)r, b = (2uv)r, (2) c = (u2 + v2)r, 66 ТЕОРИЯ ЧИСЕЛ гл. I где r Ч некоторый рациональный множитель пропорциональности.

Итак, если числа (a, b, c) образуют пифагорову тройку, то они соответственно пропорциональны числам вида v2 - u2, 2uv, u2 + v2. Обратно, легко проверить, что всякие три числа (a, b, c), определенные равенствами вида (2), образуют пифагорову тройку, так как из равенств (2) следует a2 = (u4 - 2u2v2 + v4)r2, b2 = (4u2v2)r2, c2 = (u4 + 2u2v2 + v4)r2, так что a2 + b2 = c2.

Этот результат можно несколько упростить. Из некоторой пифагоровой тройки (a, b, c) легко выводится бесконечное множество других пифагоровых троек (sa, sb, sc), каково бы ни было целое положительное s.

Так, из (3, 4, 5) получаются (6, 8, 10), (9, 12, 15) и т. д. Такие тройки не являются существенно различными, так как соответствуют подобным треугольникам. Мы условимся говорить о примитивной пифагоровой тройке, если числа a, b и c не имеют общего множителя. Можно показать, что формулы a = v2 - u2, b = 2uv, c = u2 + v2, где u, v Ч произвольные целые положительные числа (v > u), не имеющие общих множителей и не являющиеся одновременно нечетными, дают нам все примитивные пифагоровы тройки.

* Упражнение. Докажите последнее утверждение.

Вот примеры примитивных пифагоровых троек:

v = 2, u = 1 (3, 4, 5), v = 4, u = 3 (7, 24, 25), v = 3, u = 2 (5, 12, 13), v = 10, u = 7 (51, 140, 149) и т. д.

В связи с рассмотрением пифагоровых чисел более или менее естественно возникает вопрос о возможности следующего обобщения задачи:

можно ли найти такие целые положительные числа a, b, c, которые удовлетворяли бы уравнению a3 + b3 = c3, или уравнению a4 + b4 = c4, или, вообще говоря, уравнению an + bn = cn, (3) где показатель n Ч целое число, большее 2 Ответ был дан Ферма, который пришел к нему умозрительным путем. Ферма изучал одно сочинение Диофанта, известного математика древности, занимавшегося теорией чисел, и имел обыкновение делать примечания на полях книги.

Хотя он не затруднял себя тем, чтобы приводить тут же доказательства з 4 АЛГОРИТМ ЕВКЛИДА многих высказанных им теорем, но все они постепенно в дальнейшем были доказаны Ч за одним весьма значительным исключением. По поводу пифагоровых чисел Ферма сделал пометку, что уравнение (3) неразрешимо в целых числах, если n > 2, но что найденное им остроумное доказательство этой теоремы слишком длинно, чтобы его можно было поместить на полях книги, с которой он работал.

Это утверждение Ферма в его общей форме никогда и никем впоследствии не было ни доказано, ни опровергнуто, несмотря на усилия целого ряда крупнейших математиков.1 Правда, теорема была доказана для очень многих значений n, в частности, для всех n < 619, но не для всех возможных значений n; вместе с тем не было указано и примера, опровергающего теорему. Хотя сама по себе теорема и не имеет очень большого значения в математическом смысле, но попытки доказать ее положили начало многим важнейшим исследованиям в области теории чисел. Проблема вызвала большой интерес и в более широких кругах Ч отчасти благодаря премии размером в 100000 марок, предназначенной для лица, которое впервые даст решение, причем присуждение премии было поручено Геттингенской Академии. Пока послевоенная инфляция в Германии не свела на нет денежную ценность этой премии, ежегодно представлялось громадное число решений, содержащих ошибки.

Даже специалисты-математики не раз были введены в заблуждение и представляли или публиковали доказательства, которые затем отпадали после обнаружения в них иной раз каких-нибудь поверхностных недосмотров. Со времени падения курса марки ажиотаж вокруг проблемы Ферма несколько приутих; и все же пресса не перестает время от времени осведомлять нас о том, что решение найдено каким-нибудь новоявленным гением.

з 4. Алгоритм Евклида 1. Общая теория. Читатель прекрасно знаком с обыкновенной процедурой длинного деления одного целого числа a на другое число b и знает, что эту процедуру можно продолжать до тех пор, пока остаток не станет меньше, чем делитель. Так, если a = 648 и b = 7, то мы получаем частное q = 92 и остаток r = 4.

648 63 92 648 = 7 92 + 4.

Теорема Ферма была доказана в 1995 г. Подробную историю доказательства этой теоремы можно найти в книге: Сингх С. Великая теорема Ферма. Ч М.: МЦНМО, 2000. Ч Прим. ред. наст. изд.

68 ТЕОРИЯ ЧИСЕЛ гл. I По этому поводу можно сформулировать следующую общую теорему:

если a и b Ч целые числа, причем b отлично от нуля, то можно всегда найти такое целое число q, что a = b q + r, (1) где r есть целое число, удовлетворяющее неравенству 0 r < b.

Докажем эту теорему независимо от процедуры длинного деления. Достаточно заметить, что число a или само есть кратное числа b, или же лежит между двумя последовательными кратными b, bq < a < b(q + 1) = bq + b.

В первом случае равенство (1) оправдывается, причем r = 0. Во втором случае из первого неравенства вытекает, что a - bq = r > 0, а из второго Ч что a - bq = r < b, так что число r в этом случае удовлетворяет условию 0 < r < b.

Из указанного обстоятельства можно вывести большое число различных важных следствий. Первое из них Ч это метод для нахождения общего наибольшего делителя двух целых чисел.

Пусть a и b Ч два каких-то целых числа, не равных одновременно нулю; рассмотрим совокупность всех чисел, на которые делятся и a и b. Эта совокупность, несомненно, конечная, так как если, например, a = 0, то никакое число, большее чем a, не может быть делителем a.

Отсюда следует, что число общих делителей a и b конечно; пусть через d обозначен наибольший из них. Число d называется общим наибольшим делителем a и b, и мы условимся обозначать его d = (a, b). Так, если a = 8, b = 12, то непосредственная проверка показывает, что (8, 12) = 4; если a = 5, b = 9, то мы точно так же получаем (5, 9) = 1. Если a и b Ч достаточно большие числа, например a = 1804, b = 328, то попытки найти общий наибольший делитель с помощью непосредственных проб довольно утомительны. Короткий и вполне надежный метод вытекает из алгоритма Евклида. (Алгоритмом называют всякий систематизированный прием вычисления.) Он основан на том обстоятельстве, что из соотношения вида a = b q + r (2) необходимо следует, что (a, b) = (b, r). (3) В самом деле, всякое число u, которое одновременно делит и a и b, a = su, b = tu, делит также и r, так как r = a - bq = su - qtu = (s - qt)u; и обратно, всякое число v, которое одновременно делит b и r, b = s v, r = t v, з 4 АЛГОРИТМ ЕВКЛИДА делит также и a, так как a = bq + r = s vq + t v = (s q + t )v. Значит, каждый общий делитель a и b есть вместе с тем общий делитель b и r, и обратно. Но раз совокупность всех общих делителей a и b совпадает с совокупностью всех общих делителей b и r, то ясно, что общий наибольший делитель a и b должен совпадать с общим наибольшим делителем b и r. А это и выражено равенством (3). Мы сейчас убедимся в полезности установленного обстоятельства.

Для этого вернемся к примеру нахождения общего наибольшего делителя чисел 1804 и 328. Обыкновенное длинное деление 1804 1640 приводит нас к заключению, что 1804 = 5 328 + 164.

Отсюда в силу (3) следует, что (1804, 328) = (328, 164).

Заметим, что задача вычисления общего наибольшего делителя (1804, 328) заменена теперь аналогичной задачей, но для меньших чисел. Можно продолжать эту процедуру. Так как 328 328 то мы получаем дальше 328 = 2 164 + 0, так что (328, 164) = (164, 0) = = 164. Значит, (1804, 328) = (328, 164) = (164, 0) = 164, и общий наибольший делитель найден.

Эта самая процедура нахождения общего наибольшего делителя двух чисел в геометрической форме описана в Началах Евклида. Мы дадим ее общее описание в арифметической форме, исходя из произвольных целых чисел a и b, которые оба одновременно не равны нулю.

Так как сразу ясно, что (a, 0) = a, то можно допустить, что b = 0.

Последовательные деления приводят нас к цепи равенств a = bq1 + r1 (0 < r1 < b) b = r1q2 + r2 (0 < r2 < r1) (4) r1 = r2q3 + r3 (0 < r3 < r2) r2 = r3q4 + r4 (0 < r4 < r3)..................

Деление продолжается, пока какой-нибудь из остатков r1, r2, r3,... не обратится в нуль. Рассматривая неравенства, выписанные справа, мы 70 ТЕОРИЯ ЧИСЕЛ гл. I видим, что последовательно получаемые остатки образуют убывающую последовательность положительных чисел:

b > r1 > r2 > r3 > r4 >... > 0. (5) Отсюда ясно, что после конечного числа делений (нужно сделать не более b операций, но часто гораздо меньше, так как разности между соседними r обыкновенно превышают единицу) должен получиться остаток 0:

rn-2 = rn-1qn + rn, rn-1 = rnqn+1 + 0.

Как только это получилось, мы можем утверждать, что (a, b) = rn;

другими словами, общий наибольший делитель (a, b) равен последнему остатку в последовательности (5). Это следует из многократного применения равенства (3) к соотношениям (4); в самом деле, из этих соотношений следует:

(a, b) = (b, r1), (b, r1) = (r1, r2), (r1, r2) = (r2, r3), (r2, r3) = (r3, r4),..., (rn-1, rn) = (rn, 0) = rn.

Упражнение. Выполните алгоритм Евклида с цепью нахождения общего наибольшего делителя чисел: а) 187, 77; б) 105, 385; в) 245, 193.

Из равенств (4) можно вывести одно чрезвычайно важное свойство общего наибольшего делителя (a, b): если d = (a, b), то можно найти такие целые положительные или отрицательные числа k и l, что d = ka + lb. (6) Чтобы убедиться в этом, рассмотрим последовательные остатки (5).

Первое из равенств (4) нам дает r1 = a - q1b, так что r1 может быть записано в форме k1a + l1b (в данном случае k1 = 1, l1 = -q1). Из следующего равенства получается r2 = b - q2r1 = b - q2(k1a + l1b) = (-q2k1)a + (1 - q2l1)b = k2a + l2b.

Очевидно, такое же рассуждение можно по очереди применить ко всем остаткам r3, r4,..., пока мы не придем к представлению rn = ka + lb, которое и желали получить.

Pages:     | 1 |   ...   | 8 | 9 | 10 | 11 | 12 |   ...   | 76 |    Книги по разным темам