Операции над вычетами

Введем на множестве операции сложения и умножения.

Суммой классов вычетов а и b из назовем класс вычетов содержащий число а + Ь, то есть а + b = а + Ь.

Например, для классов вычетов по модулю 8, в соответствии с введенным определением верно, что:

J ₊ 4 = 9 = l,

По модулю 3: 5+4=9= 0.

Произведением классов вычетов а и b из назовем класс вычетов, содержащий число а • Ь, то есть

а • b = а • Ь. (2.157)

Например, для классов вычетов по модулю 8, имеем:

5 • 4 = 20 = 4

Соответственно, для классов вычетов по модулю 3, верным будет:

5 - 4 = 20 = 2.

Применив правило перемножения классов вычетов многократно, очевидно, получаем:

а^п = а* (2.158)

Рассмотрим несколько задач на применение правил сложения, перемножения и возведения в натуральную степень вычетов одного и того же класса.

Например, докажем, что

(₄₉юо _ ₁₄50) ; ₅

Решение. Для того, что бы доказать, что число 49¹⁰⁰ — 14⁵⁰ нацело разделится на 5, нам, очевидно, следует доказать, что это число «сидит» в классе 0.

Значит, «работаем» по mod 5.

Напомним, что если 0 = а, то это означает, что а = 5 к (к - любое целое). Имеем:

• -------------- ------ ----- ---100 ---50 -----100 -----50
• 49100 _ ₁₄50 ₌ 49100 _ ₁₄50 _{= 49} - 14 = (-1) - (-1)

= (-1)¹⁰⁰ - (-1)⁵⁰ = +Ї - Ї = 1-1 = о

(Поясним, 49 = —1 так как их разность кратна 5, т.е. они отстоят друг от друга на число кратное 5. И так же 14 = —1 , так как 14 — (—1) = +15 • 5)

И так, получили, что

4₉ioo _ 1450 — Q

Что и доказывает требуемое:

(49100 _ ₁₄50) ; ₅

Или, например, докажем, что 222⁵⁵⁵ + 555²²²делится на 7.

Решение. Рассуждая аналогично предыдущей задаче, теперь «работаем» по mod 7:

• 222^s55 + 555²²² = 222⁵⁵⁵ + 555²²² = (-2)⁵⁵⁵ + 2²²² =
• -^555 _|_ ^222 ₌₌ -ї ₊ Ї ₌ 0,

Таким образом, убедились, число 222⁵⁵⁵ 4- 555²²² действительно оказывается в классе 0, т.е. оно делится нацело на 7.

Введем обозначение: для п Є N, символом 5(п)обозначим сумму цифр числа п.

Например, 5(1002012) = 6.

Рассмотрим вопрос делимости целого числа на три и девять с точки зрения теории вычетов.

Теорема 2.42

Число п и сумма его цифр находятся в одном и том же классе вычетов по mod 3 и по mod 9:

mod 3: S(n) = п

mod 9: S(n) = n.

Доказательство (для mod 9).

Пусть n = а_ка_{к г} ... а_га₀ = а₀ + Юс^ 4- 10²а₂4-... 4-10^/ca_/c

Тогда по mod 9 имеем:

_ ---------------------------------- -- --•_ --2 __ __к__

п ⁼ По + 10п_г + 10² ? п₂ З^- ??? + 10^kn_k ⁼ clq + 10п^ + 10 ? п₂ + ••• + 10 а_к

__ так как 10 = 1

— а₀ + п-? + ••• + а_к —

Ч.т.д.

— --2 —2 -

_____________10 = 1 = 1

= а₀ + а_г+... +а_к = S(n).

Очевидно, доказательство по mod 3 аналогично.

Например, определим остаток от деления 75609121 на число 9.

Решение. Теперь уже задание - определить остаток от деления на 9, мы можем интерпретировать, как - определить в каком классе вычетов «сидит» это число по mod 9.

Работая по mod 9, имеем

• 75609121 = 7 4-5 + 64-04-94-44-24-1 = 13=4
• (1 + 2 + 6 = 9=>0)

Получили, что заданное число «сидит» в том же классе, что и 4, то есть число отличается от четверки, на число кратное 9.

Следовательно,

75609121= 9к+4 (4 - остаток)

Рассмотрим еще один пример применения теоремы.

Ответим на вопрос - может ли число, записываемое с помощью ста нулей, ста единиц и ста двоек быть точным квадратом.

Решение. По условию понимаем, что заданное число п состоит из 300 цифр:

5(п) = 0 100 4- 1-100 + 2 100 = 300

Так как

5(п) = 300 : З, ТО П : 3.

Но если п : 3 и если предположить, что п = к², то к²должно быть кратно девяти, к² • 9, то есть п должно делиться на 9.

Но S(n)=300 не кратно 9, следовательно, число записываемое с помощью ста нулей, ста единиц и ста двоек нельзя представить квадратом.

Далее, рассмотрим применение теории вычетов при определении делимости целого на одиннадцать.

Введем обозначение: для п Є N символом ?(п) обозначим знакочередующуюся сумму цифр числа, начиная с единицы.

То есть, для числа п = а_к ...а₂а_га₀ (черту поставили снизу, чтобы не путать с вычетом) знакочередующаяся сумма цифр будет выглядеть следующим образом:

У (и) = а₀ — а_г + а₂ — а₃+... +(—1)^ка_к

Теорема 2.43

Число п Є N и знакочередующаяся сумма его цифр ?(п) принадлежат одному и тому же классу вычетов по mod 11:

mod 11: п = ^(п)

Доказательство.

Так как по mod 11, верно, что

10 = (—1) = —1,то

п = а₀ 4- 10а₁ 4- 10²а₂ + —I- 10^ка_к=

= а₀ — + + а₂ — а₃ Ч-----1- (—1)^ка_к

=Е(п)

Ч.т.д.

Например, докажем, что разность числа, имеющего нечетное количество цифр и числа, записанного теми же цифрами, но в обратном порядке всегда делится на 99.

Решение. Рассмотрим число п = а_к ...а^ао, и согласно условию задачи запишем число Пі = а_оа₁ ...а_к.

Нам следует доказать, что (п — пД • 99.

Но, (и — пД • 99 означает, что п — делится нацело и на 9 и на 11 (т.к. 9 и 11 взаимно простые)

«Работаем» по mod 9:

п — = п — п₁ = S(n) — 5(пД = 0 ,

то есть

(п — пД • 9.

Теперь, по mod 11:

n - гц = п - Й7 = ?(п) ^_ Х(^і) = О-то есть

П — : 11 => И — Пі : 99.

Но, так как (п — пД • 9 и п — n_± • 11, то п — гц • 99.

В качестве примера, ответим на вопрос - можно ли число 1998 представить в виде разности квадратов двух целых числе?

Решение. Запишем задание так, возможно ли, что 1998 = а² — Ь², где а,Ь Є Z ? Очевидно, мы должны показать, что и левая и правая часть равенства может «сидеть» в одном классе вычетов по некоторому модулю.

Работаем по mod 4: 1998 = 98 = 2.

То есть число 1998 «сидит» в классе 2.

Запишем в табличку классов вычетов для целых х и х² по mod 4:

То есть, каким бы ни был х, он лежит в одном из классов по mod 4: 0,1,2,3. Тогда как квадраты х лежат в 0 и 1.

Рассмотрим все варианты разности классов числа а²(то есть 0 и 1) и числа Ь² (также 0 и 1).

• 0-0 = 0;
• 0 - Ї = 0 - 1 = = -й

Ї - 0 = 1 - 0 = Ї;

ї - Ї = 1 - 1 = 0.

Составим табличку табличка классов вычетов по mod 4 для чисел видаг = а² — Ь²:

То есть, приходим к выводу, что по mod 4 разность а² - Ь² в классе 2 никогда находиться не будет. Иначе говоря, число 1998 нельзя представить в виде разности квадратов двух целых чисел.

Продолжим далее изучение теории.

Теорема 2.44

Множество классов вычетов по модулю т образуют коммутативное кольцо с единицей относительно операций сложения и умножения классов вычетов.

Доказательство.

1) Поскольку операции сложения и умножения классов вычетов на множестве сводится к операциям соответственно сложения и умножения над числами (что следует из определения), а на множестве целых чисел эти 216

операции коммутативны и ассоциативны (операция умножения дистрибутивна относительно операции сложения), то заключаем, что и на множестве 2_таналогичные свойства справедливы.

• 2) б - нулевой элемент в Z_m;
• 3) для а противоположным является =а, причем а = =а
• 4) единичный элемент Ї.

Указанные свойства и определяют как коммутативное кольцо с единицей.

Кольцо называют аддитивной группой классов вычетов по модулю т.