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