О. ОРЕ - Приглашение в теорию чисел
Разумеется, двоичная система, используемая в ЭВМ, является той же самой системой, которую мы обсуждали в предыдущем параграфе, однако используемая терминология носит более технический оттенок. Двоичные цифры 0, 1 называются битами, что является сокращением английского выражения Binary digiTs (двоичные цифры). Так как существуют лишь две возможности: 0 и 1 в каждой позиции, то часто говорят об элементе с двумя состояниями.
Если следовать общему правилу, изложенному в § 2 этой главы, то представление данного числа в двоичной системе довольно просто. Например, возьмем N = 1971. Повторное деление на b = 2 дает
1971 = 985 • 2 + 1,
985 = 492 • 2 + 1,
492 = 246 • 2 + 0,
246 = 123 • 2 + 0,
123 = 61 • 2 + 1,
61 = 30 • 2 + 1,
30 = 15 • 2 + 0,
15 = 7 • 2 + 1,
7 = 3 • 2 + 1,
3 = 1 • 2 + 1,
1 = 0 • 2 + 1,
Следовательно,
197110 = (1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1)2.
Ранее мы отмечали, что в двоичной системе числа имеют более длинные выражения, следовательно, становится труднее с первого взгляда оценить величину числа. По этой причине в языке ЭВМ часто используется восьмеричная система счисления (с основанием 8). Это является лишь незначительным изменением двоичной системы, которое получается разбиением бит в числе на группы по три. Это можно представить себе как систему с основанием
b = 8 = 23.
Коэффициентами при этом являются восемь чисел
0 = 000, 4 = 100, 1 = 001, 5 = 101, 2 = 010, 6 = 110, 3 = 011, 7 = 111.
В качестве иллюстрации возьмем число 1971 из рассмотренного выше примера; в восьмеричной системе оно представляется как
1971 = 011, 110, 110, 011 = (3, 6, 6, 3)8.
Таким образом, этот способ записи незначительно отличается от предыдущего. В действительности, такое деление на группы нам хорошо знакомо по обычным десятичным числам: при записи и произнесении большого числа мы обычно делим его цифры на группы по три, например,
N = 89 747 321 924.
Таким образом, можно сказать, что это является представлением нашего числа при основании b = 1000= 103.
В компьютерах иногда используются и другие представления чисел. Предположим, что мы хотим записать десятичное число, скажем, N = 2947, в ЭВМ, работающей в двоичной системе. Тогда, вместо того чтобы полностью менять N на двоичное число, можно было бы изменить лишь цифры этого числа
2 = 0010,
9 = 1001,
4 = 0100,
7 = 0111
и, таким образом,
N = 0010, 1001, 0100, 0111.
Такие числа известны как кодированные десятичные числа. Этот метод иногда называется «системой 8421», так как эти десятичные цифры представляются в виде сумм двоичных единиц
0 = 0000, 1 = 0001, 2 = 0010,
22 = 4 = 0100, 23 = 8 = 1000.
Такие кодированные десятичные числа неудобны для всех видов вычислений, но не всегда целью ЭВМ являются вычисления. Тем же образом, любая буква алфавита или любой другой символ могут быть приписаны какому-нибудь двоичному числу. Это означает, что любое слово или предложение можно запоминать как двоичное число. Таким образом, если бы мы были соответствующим образом натренированы и имели бы дело со столь же подготовленной аудиторией, то могли бы общаться лишь с помощью бит.
Система задач 6.5.
1. Найдите двоичное представление чисел Ферма (§ 3, гл. 2)
2. Найдите двоичные представления четных совершенных чисел (§ 4, гл. 3)
§ 6. Игры с числами
Существует множество видов игр с числами, некоторые из которых были известны еще в средние века. Большинство из них не представляет интереса для теории чисел, скорее всего, они подобно магическим квадратам принадлежат к классу кроссвордов с числами. Некоторые из них проиллюстрируем примерами.
Перед вами телеграмма, посланная школьником домой, с настоятельной просьбой:
S E N D
M O R E
_________
M O N E Y[11]
Будем рассматривать эту схему, как сложение двух четырехзначных чисел SEND и MORE, в сумме дающих число MONEY. Каждая буква означает определенную цифру. Задача состоит в том, чтобы определить, какие это цифры. Так как всего 10 цифр, то в каждой такой задаче может фигурировать не более 10 букв, в этом примере 8. В идеальном случае задача должна иметь единственное решение.
В нашем примере очевидно, что M = 1, так как М — первая цифра либо суммы S + М, либо S + M+1, где S и М — числа, не превосходящие числа 9. Тогда для числа S имеются две возможности:
S = 9 или S = 8,
так как либо S + 1, либо S + 1 + 1 есть двузначное число. Установим сначала, что S не может быть цифрой 8, ибо, если бы S было 8, то должен был бы быть перенос из колонки сотен, что дает
S + M + 1 = 8 + 1 + 1 = 10
при сложении в колонке сотен. Следовательно, О должно было бы быть нулем и наше послание читалось бы так:
8 Е N D
1 0 R Е
_________
1 0 N Е Y
Но, исследуя колонку сотен, находим, что обязательно должен быть перенос из колонки десятков (иначе Е + 0 = Е, а не N), и так как Е ≤ 9, то
E + 0 + 1 = 10.
Это вынудило бы нас положить N = 0, но мы уже знаем, что О = 0, поэтому такой случай невозможен, и мы заключаем, что S = 9, и послание теперь читается так:
9 Е N D
1 0 R E
_________
1 0 N Е Y
Так как Е ≠ N, то сложение в колонке сотен приводит к условию E + 1 = N,
и
9 Е E+1 D
1 0 R Е
____________
1 0 E+1 Е Y
Сложение в колонке десятков дает либо
E + 1 + R = 10 + E, либо E + 1 + R + 1 = 10 + E.
Первый случай невозможен, так как он дает R = 9, что противоречит тому, что S = 9. Во втором случае R = 8, и послание читается так:
9 Е Е+1 D
1 0 8 E
____________
1 0 E+1 Е Y
И наконец, сумма в колонке единиц такова:
D + E = 10 + Y.
Для трех букв D, E, Y остаются только значения 2, 3, 4, 5, 6, 7. Наибольшая сумма двух различных чисел из них равна 13. Отсюда существует всего две возможности для Y: либо Y = 2, либо Y = 3. Последний случай невозможен, так как при этом D + E = 13, но мы не можем иметь E = 7, так как тогда N = E + 1 = 8 = R; также не может быть D = 7, так как тогда E = 6 и N = E + 1 = 7 = D.
Таким образом, Y = 2 и D + E = 12. Из имеющихся цифр 2, 3, 4, 5, 6, 7 единственной парой, в сумме дающей 12, являются 5 и 7. Так как Е ≠ 7, то это означает, что D = 7, Е = 5 и, таким образом, единственное решение нашей задачи следующее:
9 5 6 7
1 0 8 5
_________
1 0 6 5 2
Этот процесс довольно сложен, во многих случаях можно получить решение гораздо более простым путем.
Система задач 6.6.
1. Попытайтесь проанализировать следующие при-
меры только что показанным методом:
1. S Е N D
M O R E
G O L D
_________
M O N E Y
2. H O C U S
P O C U S
___________
P R E S T O
3. F O R T Y
T E N
T E N
_________
S I X T Y
4. A D A M
A N D
E V E
A
_______
R A F T
5. S E E
S E E
S E E
Y E S
_______
E A S Y
Переводы этих ребусов таковы:
1. «Шлите больше золотых монет», 2. «Фокус — Покус — Престо», 3. «Сорок + десять + десять = шестьдесят», 4. «Адам и Ева на плоту», 5. «Смотри, смотри, смотри. Да! Легко».
Если хотите, попробуйте придумать свои ребусы. Если вы знакомы с ЭВМ, то попытайтесь запрограммировать решение таких задач.
ГЛАВА 7
СРАВНЕНИЯ
§ 1. Определение сравнения
Теория чисел имеет свою алгебру, известную, как теория сравнений. Обычная алгебра первоначально развивалась как стенография для операций арифметики. Аналогично, сравнения представляют собой символический язык для делимости, основного понятия теории чисел. Понятие сравнения впервые ввел Гаусс.
