Д. Кнут - Искусство программирования том 1 (1119450), страница 16
Текст из файла (страница 16)
Кгассевсва)ег).) Докажите, что /(х+ЧзКх+Чз) (х+РсКх+Чз) (х+РсКх+Рз)'с пеэ (У+Ч»КУ+Чз) (У+РсКУ+Чз) (У+РсКУ+Рз) (з+ ЧзКз+ Чз) (з+ РсКз+ Чз) (э+ РсКз + Рз) = (х — уКх — зКу — зКРс — чзКРс — чзКРз — чз), н обобщите это равенство для определителя матрицы размера и х и, зависящего от Зп — 2 переменных хм ..., а, Рс, ..., р с, Чз, ..., Ч„. Сравните полученную формулу с результатом упр. 38. 1.2 4.
Целочисленные функции и элементарная теория чисел Для произвольного действительного числа х введем следующие абозначеяня: [х] — наибольшее целое, которое меньше нли равно х ( "пал" [](аог) х); [х] — наименьшее целое, которое больше нлн равно х ( "паглалок" (сезуслу) х). До 1970 года запись [х] часто использовалась для обозначения одной из этих двух функций, но обычно для первой.
Приведенные выше обозначения, введенные К. Ю. Айверсоном в начале 60-х годов, более удобны потому, что на практике Функции [х] н [х] встречаются одинаково часта. Функцию [х] иногда называют целой часпм ю числа х. Приведем формулы и примеры, которые очень легко проверить: 1 1 1 ~~12) =1, )~/21 = 2 (+-) = О ~ — -) =О, ~ — — ) = — 1 (а не нулю!); (х) = (х) тогда и только тогда, когда х — целое число; (х) = '1х) + 1 тогда и только тогда, когда х не является целым числом; '1-х) = — (х); х — 1 < (х) < х < (х) < х + 1. В упражнениях, приведенных в конце раздела, даны также другие важные формулы, которые связаны с операщсями "пол" и "потолок" Дня произвольных действительных чисел х и у определим следующую бинарную операцию: х той у = х — у (х(у), если у ф О; х пюй О = х.
Из этого определения видно, что если у ф О, то х ~х~ хпсой у д у у (2) Следовательно, а) если у > О, то О < х пюй у < у; Ъ) если у < О, то О > х пюй д > у; с) величина х — (х пюй у) является целочисленным кратным у. Выражение х пюс1 у называетсн оспсапском от деления х на д: аналогично 1х/у) называется часгпнмм. Если х и у являются целыми числами, то ьщой" — это знакомая нам операция: 5 псой 3 = 2, 13 спой 3 = О, — 2 пюй 3 = 1. (4 Сап х = сап (х пюй я). Величина х пюй 1 — это дробная часть числа х. Из (1) получаем, что х = 1х) + (х пюй 1). В работах по теории чисел сокращение "спой" часто используется в несколько ином, хотя и близком смысле.
Для описания теоретико-числового понятия сравнимостпь (конгруэнтность) будем применять следующую запись: х = д (по модулю х). (5) Это означает, что х пюй х = у пюй х, т. е. х — у — целое число, кратное х. Запись (5) читается следующим образом: 'х сравнимо с у по модулю х". Имеем х той у = О тогда и только тогда, когда х кратно у, т. е. тогда и только тогда, когда х делится на д. Запись у1х читается как "у делит х", т. е.
у — это положительное целое число и х спой у = О. Операция "спой" применяется также в том случае, когда х и у принимают произвольные действительные значения. Например, для тригонометрических функций можно записать следующее: А теперь перейдем к рассмотрению основных свойств сравнений, которые будут использоваться в доказательствах, основанных на фактах из теории чисел. Предполагается, что в приведенны,х ниже формулах все переменные являются целыми числами. Целые числа х и у называются взаимно иростыма, если у них нет общих множителей, .т. е. если их наибольший общий делитель равен 1. Для обозначения этого понятия будем использовать следующую запись: х .ь у.
На самом деле понятие взаимной простоты целых чисел всем хорошо знакомо; когда мы говорим, что дробь "несократима", это означает, что числитель и знаменатель — взаимно простые числа. Свойство А. Если а э— з Ь и х = у, то а х х = 6 х у и ах = Ьу (по модулю т), Свойство В. Если ах = Ьу и а = Ь н если а .Л. т, то х = у (по модулю ги).
Свойство С. а = Ь (по модулю т) тогда и только тогда, когда ап э— л 6п (по модулю тп) при и ф О. Свойство Т1. Если г .1. з, то а = Ь (по модулю гз) тогда и только тогда, когда а = 6 (по модулю г) и а = 6 (по модулю з). Свойство А говорит о том, что мы можем выполнять сложение, вычитание и умножение по модулю т точно так же, как при выполнении обычных операций сложения, вычитания и умножения. Свойство В касается операции деления и утверждает, что операция сравнения позволяет также выполнять сокращение на общий множитель в случае, если этот множитель и модуль — взаимно простые числа.
Свойства С и П указывают на то, что происходит при изменения модуля. Они доказываются в приведенных ниже упражнениях. Следующая важная теорема является следствием свойств А и В. Теорема г' (Теорема Ферма, 1640). Если р — простое число, то аз: — а (по модулю р) для всех целых а. Доказательство. Если а кратно р', то, очевидно, аг = О = а (по модулю р). Поэтому достаточно рассмотреть случай, когда а шобр ф О. Так как р — простое число, то а 1.
р. Рассмотрим следующие числа: (6) Ошобр, апюбр, 2ашодр, ..., (р — 1)агпобр. Все эти р чисел различны, так как если бы ах шеар = ау шобр, то по определению (5) ах = ау (по модулю р); следовательно, согласно свойству В х э— з у (по модулю р). Таким образом, последовательность (6) представляет собой р различных неотрицательных чисел, меньших, чем р; причем первое число — нуль, а все остальные— упорядоченные определенным образом целые числа 1, 2, ..., р — 1.
Следовательно, согласно свойству А (а)(2а) ... ((р — 1)а) = 1 2... (р — 1) (по модулю р). (7,1 Умножая обе части этого сравнения на а, получим аг(1 2... (р — 1)) = а(1 2 ... (р — 1)) (по модулю р). (8) Это доказывает теорему, поскольку каждый нз множителей 1, 2, ..., р — 1 взаимно прост с р, поэтому на основании свойства В его можно сократить. ) УПРАЖНЕНИЯ 1. [00) Чему равны [1.1), [ — 1.1), [ — 1.1], [0.99999) и [1835)? 2. [01] Чему равно [[х]]? 3.
[М10] Пусть и — целое, а х — действительное число. Докажите, что: а) [х] < и тогда и только тогда, когда х < и; Ь) и < [х] тогда и только тогда, когда и < х; с) ]х] < и тогда и только тогда, когда х < и:, г1) и < [х] тогда и только тогда, когда и < х; е) [х] = и тогда и только тогда, когда х — 1 < и < х, а также тогда и только тогда, когда и<я<и+1; 1) [х] = и тогда и только тогда, когда х < и < х+1, а также тогда и только тогда, когда и — 1<х<и.
[Эти формулы являются самыми важными ивструмгвтами доказательства утверждений, касающихся [х] и [х].] 4. [М10) Используя предыдущее упражнение, докажите, что [ — х] = — [х]. 5. [10] Пусть х — положительное действительное число. Найдите простую формулу округления х до блихсаашего целого числа . Искомое правило округлении должно даваль [х) в случае, если х шод 1 < -', и ]х], если х шог(1 > -'.
Вы должны получить единую формулу, включающую в себя оба случая. Рассмотрите, как ваша формула будет выполнять округление для отрицательного х. 6. [30] Какие из следующих равенств верны для всех положительных действительных чисел х: (а) [чгг[х] ) = [,Р); (Ь) Гь1Г )1 = [ Р1; (с) [згг[х] 1 = Г,/ 17 Т. [М15) Покажите, что [х] + [у) < [х+ у] и что это соотношение становится равенством тогда и только тогда, когда х шос1 1 + у шос( 1 < 1.
Выполняется ли аналогичная формула для функции "потолок"? 8. [00] Чему равно 100 шоб 3, 100 шоб 7, — 100 шос(7, — 100 шаг(О? 9. [05] Чему равно 5 шоб — 3, 18 шод — 3, — 2 шоб — 3? ь 10. [1О] Чему равно 1.1 гпос( 1, 0.11 шо4.1, 0.11 шой —.1? 11. [00] Что означает выражение "х ы у (по модулю 0)" согласно принятому нами опре- делению? 12, [00] Какие целые числа взаимно просты с 1? 13. [М00] Будем считать, что иаиболыпий общий делитель чисел 0 и и равен ]и[.
Какие целые числа взаимно просты с О? э 14. [13] Если х гпоб 3 = 2 и х шоб 5 = 3, чему равно х пик1 15? 15. [10] Докажите, что г(хшоду) = (гх) шос) (гу). [Правило С немедленно следует из этого распределительиого закона.] 16. [М10] Пусть у ) О. Покажите, что если (х — г)/у — целое число и О < х < у, то г = х шос) у. 17. [М15) Выведите свойство А иепосредстаеиио из определения сравиимости и докажите первую половину свойства Вс если а гя 6 (по модулю гг), то а = Ь (по модулю г) и а ьз Ь (по модулю г). (Здесь г и г — произвольные целые числа.) 18. [М15) С помощью свойства В докажите вторую половину свойства Еч если а эз 6 (по модулю г) и а = Ь (по модулю г), то а = Ь (по модулю в~) при условии, что г 1 г. ь 19. [М10) (Закон сущесгиааеанил обрашного элемеюиа.) Если и .1 т, то существует такое целое и', что ии' = 1 (по модулю гп).
Докажите это с'помощью обобщенного алгоритма Евклида (алгоритм 1.2.1Е). 20. [М1б] Докажите свойство В с помощью свойства А и закона существования обратного элемента. 21. [М22] (Основная теорема арифметики.) С помощью свойства В н упр. 1.2.1 — 5 докажите, что любое целое число и > 1 можно единсглвенннм образом (если не учитывать порядок сомножителей) представить в виде произведения простых чисел. Другими словами, покажите, что существует ровно один способ записи и = ргрг .. ры где каждое рз— простое число и рг ( рг ~ < Ры » 22. [М10] Приведите пример того, что свойство В не всегда выполняется в случае.
если а и ги не являются взаимно простымн. 23. [М10] Приведите пример того, что свойство П не всегда выполняется, если г и з не являются взаимно простыми. » 24. [М20] Допускают ли свойства А, В, С и 11 такое обобщение, чтобы они выполнялись не только для целых, но и для произвольных действительных чнселу 25. [М02] На основании теоремы Р покажите, что а" ' той р = [а не кратно р] для любого простого числа р. 20. [М1б] Пусть р — нечетное простое число, а — произвольное целое и Ь = а~» 01г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
