Книги по разным темам
Pages: | 1 | ... | 9 | 10 | 11 | 12 | 13 | ... | 76 | В качестве примера рассмотрим алгоритм Евклида в применении к нахождению (61, 24): общий наибольший делитель есть 1, и интересующее нас представление числа 1 получается из равенств 61 = 2 24 + 13, 24 = 1 13 + 11, 13 = 1 11 + 2, 11 = 5 2 + 1, 2 = 2 1 + 0.
з 4 АЛГОРИТМ ЕВКЛИДА Первое из этих равенств дает 13 = 61 - 2 24, второе Ч 11 = 24 - 13 = 24 - (61 - 2 24) = -61 + 3 24, третье Ч 2 = 13 - 11 = (61 - 2 24) - (-61 + 3 24) = 2 61 - 5 и, наконец, четвертое Ч 1 = 11 - 5 2 = (-61 + 3 24) - 5(2 61 - 5 24) = -11 61 + 28 24.
2. Применение к основной теореме арифметики. Тот факт, что d = (a, b) всегда может быть записано в форме d = ka + lb, позволит нам привести доказательство основной теоремы арифметики, отличное от того, которое было изложено на стр. 42. Сначала в качестве леммы мы докажем следствие, приведенное на стр. 43, а затем уже из него выведем теорему. Таким образом, ход мыслей будет теперь противоположен прежнему.
емма. Если произведение ab делится на простое число p, то или a, или b делится на p.
Предположим, что a не делится на p; тогда (a, p) = 1, так как p имеет лишь два делителя: p и 1. В таком случае можно найти такие целые числа k и l, что 1 = ka + lp.
Умножая обе части равенства на b, получим:
b = kab + lpb.
Так как ab делится на p, то можно написать ab = pr, так что b = kpr + lpb = p(kr + lb), и отсюда ясно, что b делится на p. Таким образом, мы установили, что если ab делится на p, но a не делится, то b непременно делится на p;
значит, во всяком случае, или a, или b делится на p, раз ab делится на p.
Обобщение на случай произведения трех или большего числа множителей не представляет труда. Например, если abc делится на p, то достаточно дважды применить лемму, чтобы получить заключение, что по меньшей мере один из трех множителей ab и c делится на p. В самом деле, если p не делит ни a, ни b, ни c, то не делит ab и, следовательно, не делит (ab)c = abc.
Упражнение. Обобщение этого рассуждения на случай произведения из произвольного числа n множителей требует явного или неявного применения 72 ТЕОРИЯ ЧИСЕЛ гл. I принципа математической индукции. Воспроизведите все детали соответствующих рассуждений.
Из полученного результата немедленно получается основная теорема арифметики. Предположим, что имеются два разложения целого числа N на простые множители:
N = p1p2... pr = q1q2... qs.
Так как p1 делит левую часть равенства, то должно делить и правую и, значит (см. предыдущее упражнение), должно делить один из множителей qk. Но qk Ч простое число; значит, p1 должно равняться qk. Сократив равенство на общий множитель p1 = qk, обратимся к множителю p2 и установим таким же образом, что он равен некоторому qt. Сократив на p2 = qt, переходим, далее, к множителю p3, и т. д. В конце концов сократятся все множители p, и слева останется 1. Так как q Ч целые положительные числа, то и справа не может остаться ничего, кроме 1.
Итак, числа p и числа q будут попарно равны, независимо от порядка;
значит, оба разложения тождественны.
3. Функция Эйлера (n). Еще раз о теореме Ферма. Говорят, что два целых числа a и b взаимно простые, если их общий наибольший делитель равен 1:
(a, b) = 1.
Например, числа 24 и 35 взаимно простые, но числа 12 и 18 не взаимно простые.
Если a и b взаимно простые, то можно подобрать такие целые числа k и l, что ka + lb = 1.
Это следует из свойства (a, b), отмеченного на стр. 64.
Упражнение. Докажите теорему: если произведение ab делится на r, причем r и a взаимно простые, то b делится на r. (Указание: если r и a взаимно простые, то можно найти такие целые числа k и l, что kr + la = 1.
Затем умножьте обе части равенства на b). Эта теорема обобщает лемму со стр. 65, так как простое число p в том и только в том случае является взаимно простым с a, если a не делится на p.
Пусть n Ч произвольное целое положительное число; обозначим через (n) количество таких целых чисел в пределах от 1 до n, которые являются взаимно простыми с числом n. Выражение (n), впервые введенное Эйлером, представляет собой очень важную теоретико-числовую функцию. Легко подсчитать значения (n) для нескольких первых зназ 4 АЛГОРИТМ ЕВКЛИДА чений n:
(1) = 1, так как 1 является взаимно простой с (2) = 1, 1 (3) = 2, 1 и 2 являются взаимно простыми с (4) = 2, 1 и 3 (5) = 4, 1, 2, 3, 4 (6) = 2, 1, 5 (7) = 6, 1, 2, 3, 4, 5, 6 (8) = 4, 1, 3, 5, 7 (9) = 6, 1, 2, 4, 5, 7, 8 (10) = 4, 1, 3, 7, 9 и т. д.
Заметим, что (p) = p - 1, если p Ч простое число; в самом деле, у числа p нет делителей, кроме 1 и p, и потому все числа 1, 2,..., p - являются взаимно простыми с p. Если n составное и его разложение на простые множители имеет вид 1 2 r n = p 1 p 2... p r, где числа p обозначают различные простые множители, каждый из которых возводится в некоторую степень, то тогда 1 1 (n) = n 1 - 1 -... 1 -.
p1 p2 pr Например, из разложения 12 = 22 3 следует 1 1 1 (12) = 12 1 - 1 - = 12 = 4, 2 3 2 что легко проверить и непосредственно. Доказательство приведенной теоремы совершенно элементарно, но мы его не приводим.
Упражнение. Пользуясь функцией Эйлера (n), обобщите теорему Ферма, приведенную на стр. 55. Обобщенная теорема формулируется следующим образом: если n Ч целое число и a взаимно просто с n, то a (n) 1 (mod n).
4. Непрерывные дроби. Диофантовы уравнения. Алгоритм Евклида, служащий для нахождения общего наибольшего делителя двух целых чисел, сразу же приводит к очень важному методу представления отношения двух целых чисел в виде некоторой сложной дроби особого вида.
Например, в применении к числам 840 и 611 алгоритм Евклида дает ряд равенств 840 = 1 611 + 229, 611 = 2 229 + 153, 229 = 1 153 + 76, 153 = 2 76 + 1, 74 ТЕОРИЯ ЧИСЕЛ гл. I которые, между прочим, показывают, что (840, 611) = 1. Но из этих равенств, с другой стороны, получаются следующие:
840 229 = 1 + = 1 +, 611 611 153 = 2 + = 2 +, 229 229 76 = 1 + = 1 +, 153 153 = 2 +.
76 Комбинируя последние равенства, мы приходим к следующему разложению числа :
840 = 1 +.
2 + 1 + 2 + Выражение вида a = a0 +, (7) a1 +.
a2 +.
.
+ an где все числа a целые положительные, называется непрерывной дробью.
Алгоритм Евклида дает метод для представления всякого рационального числа в виде такой непрерывной дроби.
Упражнение. Разложите в непрерывные дроби рациональные числа 2 43,,.
5 30 * Непрерывные дроби играют важную роль в той области высшей арифметики, которую иногда называют диофантовым анализом. Диофантово уравнение Ч это алгебраическое уравнение с одним или с несколькими неизвестными, все коэффициенты которого Ч целые числа, причем ставится задача отыскания лишь целых его корней. Такое уравнение может или вовсе не иметь решений, или иметь их конечное число, или, наконец, иметь бесконечное множество решений. Простейшее диофантово уравнение Ч линейное, с двумя неизвестными:
ax + by = c, (8) где a, b, c Ч данные целые числа, и требуется найти целые решения x, y. Полное решение уравнения этого типа может быть найдено посредством алгоритма Евклида.
Прежде всего этот алгоритм позволит нам определить d = (a, b); затем, как мы знаем, при надлежащем выборе целых чисел k и l выполняется равенство ak + bl = d. (9) з 4 АЛГОРИТМ ЕВКЛИДА Итак, уравнение (8) имеет частное решение x = k, y = l в том случае, если c = d.
Вообще, если c есть кратное d, c = d q, то из равенства (9) мы выводим a(kq) + b(lq) = dq = c, так что в этом случае уравнение (8) имеет частное решение x = x = kq, y = y = lq. Обратно, если уравнение (8) имеет при данном c хоть одно решение x, y, то c должно быть кратным d = (a, b): действительно, d делит и a и b, следовательно, должно делить c. Мы доказали, таким образом, что уравнение (8) имеет (хоть одно) решение в том и только том случае, если c кратно (a, b).
Посмотрим теперь, как, зная одно решение x = x, y = y уравнения (8), определить все прочие решения. Пусть x = x, y = y есть какое-либо иное решение; тогда x = x - x, y = y - y есть решение лоднородного уравнения ax + by = 0. (10) Действительно, из равенств ax + by = c и ax + by = c посредством вычитания получаем a(x - x) + b(y - y) = 0.
Обращаясь теперь к уравнению (10), мы видим, что общее его решение имеет rb ra вид x =, y = - где r Ч произвольное целое число. (Предоставляем (a, b) (a, b) доказательство читателю в качестве упражнения. Указание: разделите на (a, b) и воспользуйтесь упражнением на стр. 66.) Затем окончательно будем иметь общее решение уравнения (8):
rb ra x = x +, y = y -.
(a, b) (a, b) Подведем итоги. Линейное диофантово уравнение ax + by = c, где a, b и c Ч целые числа, имеет целые решения в том и только том случае, если c кратно (a, b). В этом случае частное решение x = x, y = y может быть найдено посредством алгоритма Евклида, а самое общее имеет вид rb ra x = x +, y = y -, (a, b) (a, b) где r Ч произвольное целое число.
Примеры. Уравнение 3x + 6y = 22 не имеет целых решений, так как (3, 6) = 3 не делит 22.
Уравнение 7x + 11y = 13 имеет частное решение x = -39, y = 26, которое находится с помощью следующих вычислений:
11 = 1 7 + 4, 7 = 1 4 + 3, 4 = 1 3 + 1, (7, 11) = 1, 1 = 4 - 3 = 4 - (7 - 4) = 2 4 - 7 = 2(11 - 7) - 7 = 2 11 - 3 7.
76 ТЕОРИЯ ЧИСЕЛ гл. I Отсюда следует:
7 (-3) + 11 (2) = 1, 7 (-39) + 11 (26) = 13.
Остальные решения даются формулами x = -39 + 11r, y = 26 - 7r, где r Ч произвольное целое число.
Упражнение. Решите диофантовы уравнения:
а) 3x - 4y = 29;
б) 11x + 12y = 58;
в) 153x - 34y = 51.
Г Л А В А II Математическая числовая система Введение В дальнейшем мы должны в очень значительной степени расширить понятие числа, связываемое первоначально с натуральным рядом, для того чтобы сконструировать мощный инструмент, способный удовлетворять потребностям и практики, и теории. Исторически Ч в процессе долгой и неуверенно протекавшей эволюции Ч нуль, целые отрицательные числа и рациональные дроби приобрели постепенно те же права, что и числа натурального ряда, и в наши дни правилами действий со всеми этими числами прекрасно овладевает средний ребенок школьного возраста. Но для того чтобы обеспечить полную свободу в алгебраических операциях, нужно идти и дальше и охватить расширенным понятием также иррациональные и комплексные числа. Хотя эти обобщения понятия числа употреблялись уже столетия тому назад и на них базируется вся современная математика, но на прочный логический фундамент они были поставлены лишь в недавнее время. В настоящей главе мы дадим очерк основных этапов этого развития.
з 1. Рациональные числа 1. Рациональные числа как средство измерения. Натуральные числа возникают как абстракция в процессе счета объектов, образующих конечные совокупности. Но в повседневной жизни нам приходится не только считать объекты, индивидуально отделенные один от другого, но и измерять величины, например такие, как длина, площадь, вес, время. Если мы хотим обеспечить свободу операций с результатами измерения таких величин, могущих неограниченно делиться на части, нам необходимо, не ограничиваясь натуральным рядом, расширить пределы арифметики и создать новый мир чисел. Первый шаг заключается в том, чтобы проблему измерения свести к проблеме счета. Мы выбираем сначала совершенно произвольно единицу измерения Ч фут, ярд, дюйм, фунт, грамм Ч смотря по случаю, и этой единице приписываем меру 1.
Затем мы считаем число таких единиц, входящих в измеряемую величину. Может случиться, что данный кусок свинца весит ровно 54 фунта.
78 МАТЕМАТИЧЕСКАЯ ЧИСЛОВАЯ СИСТЕМА гл. II Но в общем случае, как мы замечаем, процесс счета не сходится:
данная величина не измеряется абсолютно точно выбранной единицей, не оказывается ей кратной. Самое большее, что мы можем сказать в этом случае, Ч это то, что она заключена между двумя последовательными кратными этой единицы, допустим, между 53 и 54 фунтами. Если так действительно происходит, то мы делаем следующий шаг и вводим новые подъединицы, получающиеся от подразделения первоначальной единицы на некоторое число n равных частей. На обыкновенном языке эти новые подъединицы могут иметь те или иные названия; например, фут подразделяется на 12 дюймов, метр Ч на 100 сантиметров, фунт Ч на 16 унций, час Ч на 60 минут, минута Ч на 60 секунд, и т. д. Однако в общей математической символике подъединица, получаемая при подразделении первоначальной единицы на n частей, обозначается символом, n и если рассматриваемая величина содержит ровно m таких подъединиц, m то ее мера тогда есть. Этот символ называется дробью или отношеn нием (иногда пишут m : n). Последний, и самый существенный, шаг был совершен уже осознанно, после многих столетий накопления отдельных m усилий: символ был освобожден от его конкретной связи с процессом n измерения и самими измеряемыми величинами и стал рассматриваться как отвлеченное число, самостоятельная сущность, уравненная в своих правах с натуральным числом. Если m и n Ч натуральные числа, то m символ называется рациональным числом.
n Употребление термина число (первоначально под числами понимали только натуральные числа) применительно к новым символам оправдывается тем обстоятельством, что сложение и умножение этих символов подчиняются тем же законам, что и соответствующие операции над натуральными числами. Чтобы в этом убедиться, нужно сначала определить, в чем заключаются сложение и умножение рациональных чисел, а также определить, какие рациональные числа признаются равными между собой. Эти определения, как всем известно, таковы:
a c ad + bc a c ac a ac a + =, =, = 1, =, (1) b d bd b d bd a bc b где a, b, c, d Ч произвольные натуральные числа. Например, 2 4 2 5 + 3 4 10 + 12 22 2 4 2 4 + = = =, = =, 3 5 3 5 15 15 3 5 3 5 3 8 2 4 = 1, = =.
3 12 3 4 Эти самые определения мы вынуждены принять, если имеем в виду использовать рациональные числа для измерения длин, площадей и т. п.
Но с более строгой логической точки зрения эти правила сложения и умножения и это толкование равенства по отношению ко вновь вводимым символам устанавливаются независимо по определению, не будучи з 1 РАЦИОНАЛЬНЫЕ ЧИСЛА обусловлены какой-либо иной необходимостью, кроме взаимной совместимости (непротиворечивости) и пригодности к практическим приложениям. Исходя из определений (1), можно показать, что основные законы арифметики натуральных чисел продолжают сохраняться и в области всех рациональных чисел:
p + q = q + p (коммутативный закон сложения), p + (q + r) = (p + q) + r (ассоциативный закон сложения), pq = qp (коммутативный закон умножения), (2) p(qr) = (pq)r (ассоциативный закон умножения), p(q + r) = pq + pr (дистрибутивный закон).
Pages: | 1 | ... | 9 | 10 | 11 | 12 | 13 | ... | 76 | Книги по разным темам