Добрый день, дети. Давайте, посмотрим, сколько сейчас времени. Сколько будет через 12 часов, а еще через 12?
Представьте себе, что время на часах не «обнулялось» бы каждый день и после 24:00, было бы 25 часов и так далее. Звучит странно. Но не кажется странным то, что после одного оборота часовой стрелки, мы говорим 1 час дня или 13 часов.
Давайте посмотрим на часы и подумаем, если сейчас 9:00 утра. Сколько будут показывать часы через 8 часов. Часовая стрелка укажет нам на 5, или мы скажем, что это 9+8 = 17, т.е. 17 часов вечера. Но мы же видим на часах 5. Дело в том, что числа 5 и 17 имеют общий арифметический модуль, который равен 12. Такие модули используют в модульной арифметике. Это система арифметики для целых чисел, где числа «оборачиваются вокруг» после достижения определенной стоимости – модуля. Т.е. в примере с часами, как мы говорили раньше, модуль равен 12, при прохождении через 12, мы получаем не 5 часов, а 17.00 и т.д. Но часы ограничивают нас сутками, и мы никогда не получим 33 часа, а модульная арифметика дает нам право находить большее количество чисел, сравнимых по модулю.
Модульная арифметика используется для сравнения чисел. Сравнение чисел – тема нашего сегодняшнего занятия.
Определение: Если два целых числа и при делении на дают одинаковые остатки, то они называются сравнимыми по модулю числа .
Сравнимость чисел и записывается в виде формулы (сравнения):
Число называется модулем сравнения.
Запись можно прочитать так : а сравнимо с b по модулю m.
Для примера числа 13 и 48 сравнимы по модулю 5, так как оба числа при делении на 5, дают остаток 3:
13=5*2+3 и 48=5*9+3
Определение сравнимости чисел и по модулю равносильно любому из следующих утверждений:
1. Разность чисел и делится на без остатка;
То есть числа13 и 48 сравнимы по модулю 5, так как их разность 35 делится на 5.
2. Число может быть представлено в виде , где — некоторое целое число.
Значит, имеет место равенство: 48=13+5*7 или 48-13=5*7, т.е. разность чисел 48 и 13 делится на 5 без остатка.
Давайте попробуем, используя вышесказанное, определить, сравнимы ли два данных числа по заданному модулю? Попробуем составить алгоритм узнавания сравнимых по данному модулю целых чисел.
Ответ: Чтобы проверить сравнимость двух целых чисел по данному модулю, надо:
1. Найти разность этих чисел;
2. Установить, делится ли полученная разность на данный модуль;
3. Сделать вывод.
Проверим, сравнимы ли числа:
1. а=58, в=42, m=8 ; Проверка: 58-42 = 6, 6 не делится на 8, значит числа не сравнимы.
2. а=47, в=13, m=-2 ; Проверка 47-13 = 34, 34 делится на (-2), значит числа сравнимы.
3. а=45, в=6, m=3 ; Проверка 45-6=39, 39 делится на 3, значит числа сравнимы.
4. а=18, в=29, m=11. Проверка 18-29 = -11, -11 делится на 11, значит числа сравнимы.
Проверим, верно ли сравнение:
1. 6≡0(mod 2); проверка: 6-0=6, 6 делится на 2, числа сравнимы по модулю 2.
2. 4≡53(mod 7); проверка 4-53 = -49, -49 делится на 7, числа сравнимы по модулю 7.
3. 59≡16(mod 2), проверка: 59-16 = -43, -43 не делится на 2, числа не сравнимы по модулю 2.
Свойства сравнения по модулю:
Для фиксированного натурального числа отношение сравнимости по модулю обладает следующими свойствами:
• для любого целого справедливо a ≡ a (mod m)
• если a ≡ b (mod m), то b ≡ a (mod m)
• если a ≡ b (mod m) и b ≡c (mod m), то a ≡ c (mod m)
Кроме вышеперечисленных свойств, для сравнений справедливы следующие утверждения (теоремы, имеющие доказательства):
• Обе части сравнения можно умножать на любое целое число, при этом сравнение не изменится.
• Сравнения можно почленно складывать, вычитать, перемножать .
• Обе части сравнения можно делить на одно и то же число, отличное от нуля.
• Любое слагаемое левой и правой части сравнения можно перенести с противоположным знаком в другую часть.
• Обе части сравнения и модуль можно делить на одно и то же ненулевое число.
• Сравнения можно возводить в степень.
• Рассмотрим некоторый многочлен с целыми коэффициентами:
koxn + k1xn-1+ ... +kn-1x+kn.
Если a≡b(mod m), то значения, которые принимает этот многочлен при х=а и при x=b, также сравнимы между собой по модулю m, т. е.
koan+k1an-1+ ... kn-1a+kn≡kobn+k1bn-1+ ... kn-1b+kn (mod m).
Рассмотрим Задачу 1.
Крестьянка несла на базар корзину яиц. Неосторожный всадник, обгоняя женщину, задел корзину, и все яйца разбились. Желая возместить ущерб, он спросил у крестьянки, сколько яиц было в корзине. Она ответила, что число яиц не знает, но когда она раскладывала их по 2, по 3, по 4, по 5 и по 6, то каждый раз одно яйцо оставалось лишним, а когда она разложила по 7, лишних яиц не осталось. Сколько яиц несла крестьянка на базар?
Решение:
Пусть х – число яиц. Так как х – 1 делится на 2, на 3, на 4, на 5, на 6, то оно делится на их НОК, равное 60. Значит, х имеет вид 60у + 1. Поэтому для ответа на вопрос задачи надо решить в натуральных числах уравнение 60у + 1 = 7z.
Выразим z:
z=(60y+1):7
Значит, 60y+1⋮7
То есть, 60y≡-1(mod 7), (60y-(-1) ⋮7 – определение сравнения)
Т.к. 56y кратно 7, вычтем из левой части сравнения,
4y≡-1(mod 7), (умножим на 2 левую и правую части сравнения),
8y≡-2(mod 7), (вычтем из левой части сравнения 7y),
y≡-2(mod 7) =>
y-(-2)⋮7 (по определению)
y+2=7t, где t∈Z
Значит,
y=7t-2
Наименьшее положительное решение получаем при t = 1,
тогда y=5,
x=60*5+1
x=301
Ответ: крестьянка несла на базар 301 яйцо.
Рассмотрим Задачу 2.
Доказать, что при любом натуральном n число 122n+1 +11n+2 делится на 133.
Решение.
Мы имеем: 122n+1=122n∙12=12∙144n
Но 144≡11 (mod 133), и потому согласно свойству возведения сравнений в степень: 144n≡11n(mod 133).
Умножая на 12 (по свойству умножения сравнений), получаем: 12∙144n≡12∙11n (mod 133),
так что 122n+1≡ 12∙11n (mod 133).
Далее, 11n+2=11n∙121. А так как 121≡-12 (mod 133), то 121∙11n≡-12∙11n (mod 133), т. е. 11n+2≡-12∙11n (mod 133). Складывая сравнения (это можно делать по свойству о сложении сравнений), получаем:
122n+1 +11n+2≡12∙11n+(-12∙11n) (mod 133)≡0 (mod 133),
т. е. число 122n+1 +11n+2 делится на 133.
Рассмотрим Задачу 3.
Докажите, что при любом целом n число n3+3n2+2n делится на 6.
Решение.
Всякое целое число n дает при делении на 6 один из остатков 0, 1, 2, 3, 4, 5, т. е. имеет место одно из сравнений:
n≡0 (mod 6), n≡1 (mod 6), n≡2 (mod 6), n≡3 (mod 6), n≡4 (mod 6), n≡5 (mod 6).
Если n≡0(mod 6), то по следствию 2:
n3+3n2+2n≡03 +3∙02 +2∙0(mod 6), т.е n3+3n2+2n≡0(mod 6).
Если n≡1 (mod 6), то (опять по следствию 2)
n3+3n2+2n=l3 +3∙12 +2∙1(mod6), т. е. n3+3n2+2n=6≡0(mod 6).
Если n≡2 (mod 6), то n3+3n2+2n=23 +3∙22+2∙2(mod6), т. е.n3+3n2+2n=24≡0(mod 6).
Аналогично рассматриваются три оставшихся случая.
Итак, в любом случае n3+3n2+2n≡0(mod 6), т. е. n3+3n2+2n делится на 6.
Упражнения.
1. Докажите, что при любом целом n число n2 + n четно.
2. При каких n число n2-1 делится на 3?
3. Докажите, что если числа а и b не делятся на 3, но дают одинаковые остатки при делении на 3, то число ab-1 делится на 3. Обратно, если ab-1 делится на 3, то числа а и b не делятся на 3 и дают одинаковые остатки при делении на 3.
4. Докажите, что если числа а и bне делятся на 3 и дают разные остатки при делении на 3, то число ab+1 делится на 3. Обратно, если ab+1 делится на 3, то числа а и b не делятся на 3 и дают разные остатки при делении на 3.
5. Докажите, что, каковы бы ни были целые числа а и b, число ab(a2 -b2) всегда делится на 3.
6. Докажите, что, каковы бы ни были целые числа а и b, число ab(а2 - b2) (4а2 - b2) всегда делится на 5.
7. Докажите, что, каковы бы ни были целые числа а и b, число ab(a4 – b4) всегда делится на 5.
8. Докажите, что при любом целом n число n2 (n2- 1) делится на 4.
9. Докажите, что при любом целом n число n5 - n делится на 5.
10. Докажите, что при любом целом n число n(n6- 1) делится на 7.
11. Докажите, что если хотя бы одно из чисел а ,bне делится на 7, то и число а2+b2 не делится на 7.
12. Докажите, что при любом целом n число n(2n+1)(7n+1) делится на 6.
13. Число а дает остаток r1 при делении на m, а число b дает остаток r2 при делении на m. Можно ли утверждать, что число а+b дает остаток r1 + r2 при делении на m, а число ab дает остаток r1r2при делении на m? Как изменить формулировку, чтобы получилось верное утверждение?
Некоторые ответы и указания.
1. Всякое целое число n дает при делении на 2 один из остатков 0, 1, т. е. имеет место одно из сравнений:
n≡0 (mod 2), n≡1 (mod 2)
Если n≡0(mod 2), то по следствию 2:
n2 + n=02+0≡0(mod 2)
Если n≡1 (mod 2), то (опять по следствию 2):
n2 + n=12+1=2≡0(mod 2)
В обоих случаях остаток 0, следовательно, число n2 + n четно при любом целом n.
2. Всякое целое число n дает при делении на 3 один из остатков 0,1,2,-1,-2 т.е. имеет место одно из сравнений:
n≡0 (mod 3), n≡1 (mod 3), n≡2 (mod 3).
Если n≡0(mod 3), то по следствию 2:
n2 -1=02-1≡-1(mod 3)
Если n≡1 (mod 3), то (опять по следствию 2):
n2 -1=12-1≡0(mod 3)
Если n≡2 (mod 3), то (опять по следствию 2):
n2 -1=22-1=3≡0(mod 3) в этом случае число делится на 3.
Число n2-1 делится на 3 в тех случаях, когда n при делении на 3 дает остаток 2.
3. Всякое целое число n дает при делении на 3 один из остатков 0,1,2
Если a≡1 (mod 3), b≡1 (mod 3), то ab-1≡1∙1-1≡0(mod 3)
Если a≡2 (mod 3), b≡2 (mod 3), то ab-1≡2∙2-1=3≡0(mod 3)
Первое утверждение, верно, получили остатки 0.
Если ab-1≡0(mod 3), то ab≡1(mod 3), следовательно, a≡b (mod 3),т.к.
Если a≡1 (mod 3), b≡1 (mod 3), то ab≡1∙1≡1(mod 3)
a≡2 (mod 3), b≡2 (mod 3), то ab≡2∙2=4≡1(mod 3)
a≡2 (mod 3), b≡1 (mod 3), то ab≡2∙1=3≡0(mod 3)
a≡1 (mod 3), b≡2 (mod 3), то ab≡1∙2=3≡0 (mod 3)
a≡0 (mod 3), b≡2 (mod 3), то ab≡0∙2=0≡0(mod 3) такой же результат получим если остаток числа b будет 1, или если b будет делится на 3 , а a нет.
Получили , что a и b ,будут иметь одинаковые остатки при делении на 3.
5. ab(a2 -b2)=a3b-ab3
Всякое целое число n дает при делении на 3 один из остатков 0,1,2, т.е.
n≡0 (mod 3), n≡1 (mod 3), n≡2 (mod 3),
Тогда n≡n3(mod 3), a3b-ab3≡ab-ab(mod 3)≡0(mod 3),это означает что число ab(a2 -b2) делится на 3.
6. ab(а2-b2) (4а2-b2)=ab(4a4-a2b2-4a2b2+b4)=4a5b-5a3b3+ab5
Второе слагаемое -5a3b3 делится на 5, т.к. имеет такой множитель
Тогда n≡n5(mod 5), 4a5b+ab5≡4ab+ab(mod 5)≡5ab(mod 5)≡0(mod 5),это означает что число ab(а2-b2) (4а2-b2) делится на 5.
8. n2 (n2- 1) делится на 4.
Всякое целое число n дает при делении на 3 один из остатков 0,1,2, т.е. имеет место одно из сравнений:
n≡0 (mod 4), n≡1 (mod 4), n≡2 (mod 4), n≡3 (mod 4)
n2 (n2- 1)=n4- n2
Если n≡0 (mod 4), то n4- n2≡04-02(mod 4)≡0(mod 4).
Если n≡1 (mod 4), то n4- n2≡14-12(mod 4)≡0(mod 4).
Если n≡2 (mod 4), то n4- n2≡24-22(mod 4)≡12(mod 4)≡0(mod 4).
Если n≡3 (mod 4), то n4- n2≡34-32(mod 4)≡72(mod 4)≡0(mod 4).
это означает что число n2 (n2- 1) делится на 4.
Таким образом теорию сравнения чисел можно использовать для решения многих задач и доказательств признаков делимости чисел. Но это тема наших следующих занятий.
Какие открытия для себя вы сделали сегодня на занятии? Что понравилось больше всего? А что вызвало затруднение?
Спасибо за внимание!
|
