О. ОРЕ - Приглашение в теорию чисел

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. «Смотри, смотри, смотри. Да! Легко».

Если хотите, попробуйте придумать свои ребусы. Если вы знакомы с ЭВМ, то попытайтесь запрограммировать решение таких задач.

Теория чисел имеет свою алгебру, известную, как теория сравнений . Обычная алгебра первоначально развивалась как стенография для операций арифметики. Аналогично, сравнения представляют собой символический язык для делимости, основного понятия теории чисел. Понятие сравнения впервые ввел Гаусс.

Прежде чем мы обратимся к понятию сравнения, сделаем одно замечание о числах, которые будем изучать в этой главе. Мы начали эту книгу, заявив, что будем рассматривать целые положительные числа 1, 2, 3…, и в предыдущих главах мы ограничивались только этими числами и дополнительным числом 0. Но теперь мы достигли стадии, на которой целесообразно расширить наши границы, рассматривая все целые числа:

0, ±1, ±2, ±3….

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

Теперь вернемся к языку сравнений. Если а и b — два целых числа и их разность а — b делится на число m , мы выражаем это записью

a ≡ b (mod m ) (7.1.1)

которая читается так:

а сравнимо с b по модулю m .

Делитель m мы предполагаем положительным; он называется модулем сравнения . Наше высказывание (7.1.1) означает, что

a — b = mk , где k — целое число. (7.1.2)

Примеры.

1) 23 ≡ 8 (mod 5), так как 23 — 8 = 15 = 5 3;

2) 47 ≡ 11 (mod 9), так как 47–11 = 36 = 9 4;

3) —11 ≡ 5 (mod 8), так как — 11 — 5 = —16 = 8 (-2);

4) 81 ≡ 0 (mod 27), так как 81 — 0 = 81 = 27 3.

Последний пример показывает, что вообще, вместо того, чтобы говорить: число а делится на число m , мы можем записать

a ≡ 0 (mod m ),

так как это означает, что

а — 0 = а = mk ,

где k — некоторое целое число. Например, вместо того, чтобы сказать, что а — четное число, мы можем записать

a ≡ 0 (mod 2).

Таким же образом видно, что нечетное число является числом, удовлетворяющим сравнению

а ≡ 1 (mod 2).

Эта несколько странная терминология является довольно обычной для математических работ.

Способ, которым мы записываем сравнения, напоминает нам уравнения, и в действительности, сравнения и алгебраические уравнения имеют много общих свойств. Простейшими из них являются три следующих свойства:

a ≡ a (mod m ); (7.2.1)

это является следствием того, что

а — а = m — 0,

a ≡ b (mod m ) означает, что и b a (mod m ). (7.2.2)

Это следует из того, что b — a = — ( а — b ) = m (— k ).

Из

а ≡ b (mod m ) и b ≡ c (mod m ) (7.2.3)

следует, что а ≡ c (mod m ), потому что первые два утверждения означают, что

а — b = mk, b — с = ml ,

поэтому

а — с = ( а — b ) + ( b — с ) = m ( k + l ).

Пример . Из того, что 13 ≡ 35 (mod 11) и 35 ≡ — 9 (mod 11) следует, что 13 ≡ — 9 (mod 11).

Мы говорили, что сравнения похожи по своему свойству на равенства. В действительности, мы можем рассматривать равенства как тип сравнения, а именно, сравнения по модулю 0. По определению,

а ≡ b (mod 0)

означает, что

a — b = 0 k = 0

или

а = b .

Вы почти никогда не встретите такую форму сравнения для записи уравнений в математической литературе. Но существует другое сравнение, очевидно, довольно тривиальное, которое иногда используется. Когда модуль есть число m = 1, мы имеем, что