Как найти остаток от деления суммы чисел

Решения задач на остатки с вычислительной точки зрения можно несколько упростить, если вместо обычных остатков от деления на натуральное число n — чисел от 0 до n-1 — рассматривать «целые остатки» — целые числа, меньшие или равные по модулю, чем $frac n2$.

Например, всякое целое число можно единственным образом представить в одном из видов 7k, 7k±1,7k±2, 7k±3, или в одном из видов 8k, 8k±1, 8k±2, 8k±3, 8k+4, так что числа 0, ±1, ±2, ±3 также можно считать остатками от деления на 7, а числа 0, ±1, ±2, ±3, ±4— остатками от деления на 8. (Заметим, что число -4 в «целые остатки» не включается: число вида 8n-4 можно записать и в виде 8(n-1)+4, т.е. одно и то же число может быть представлено в двух различных видах, а такая неоднозначность противоречит всей идеологии деления с остатком.)

Для «целых остатков» остаются в силе все свойства обычных остатков, но при использовании целых остатков решение задач упрощается. Например, число 34⁷⁴⁵ при делении на 7 дает тот же остаток, что и (-1)⁷⁴⁵=-1, т.е. при переводе на язык обычных остатков — остаток 6.

Эффективно используются «целые остатки» при применении «языка сравнений»: ясно, что вычисления с ними проще, чем с обычными, потому что они меньше по модулю (в данном случае модуль — это абсолютная величина).

Остаток от деления суммы двух натуральных чисел на натуральное число k совпадает с остатком от деления на k, который при делении на k дает сумма их остатков.

Остаток от деления произведения двух натуральных чисел на натуральное число k совпадает с остатком от деления на k, который при делении на k дает произведение их остатков.

Эти свойства доказываются в одну строчку, но во втором случае используется та же группировка, что мы применяли для доказательства одного свойства сравнений. Это и неудивительно, поскольку свойства остатков и свойства сравнений — это на самом деле одни и те же утверждения, только сформулированные на разных языках.

Ясно, что эти свойства обобщаются на любое число слагаемых и сомножителей, и поэтому отсюда можно получить утверждение, важное для степеней натуральных и целых чисел:

Если число а при делении на натуральное число k дает остаток r, то числа аⁿ и rⁿ при делении на k дают равные остатки.

Поэтому, например, 34⁷⁴⁵ при делении на 7 дает тот же остаток, что и 6⁷⁴⁵, что уже немного легче. А если заметить, что 6²=36 при делении на 7 дает остаток 1, то, пользуясь свойствами степеней, легко найти остаток, который дает вся степень 34⁷⁴⁵ при делении на 7: $6^{745}=6^{744}times 6=36^{372}times 6$ и поскольку первый множитель дает остаток 1, а второй — остаток 6, то искомый остаток равен 6.

Зная эти принципы вы легко сможете делать решение задач по математике и другим направлениям.

Материалы по теме:

• Точные квадраты и кубы
• Свойства сравнений
• Малая теорема Ферма
• Признаки делимости на 4, 8, 11 и 25

Арифметика остатков

Арифметика
остатков

Статья опубликована при поддержке образовательного сайта по математике «EGEUROK.RU». Подготовка к ЕГЭ по математики – дело сложное. Далеко не в каждой школе учат решать задачи, которые ребенок видит в части С. Что бы к ним подготовится, изучите решение заданий ЕГЭ и ГИА по математике на сайте «EGEUROK.RU», по адресу http://egeurok.ru.

«Остатки» играют в нашей
жизни большую роль. Мы встречаемся с ними
буквально на каждом шагу. Приведем несколько
примеров.

1. Говоря «30 год», мы указываем
век, так как 30 год может быть и в XX в., и в XIX в.,
и в XVIII в.; 30 – это остаток от деления полного
числа лет на 100.

2. Вы взглянули на часы,
которые показывают 8 ч. Но это может быть и
8 ч и 20 ч, так как часы показывают остаток от
деления полного времени на 12.

3. Счетчик показывает 0314 кВт
• ч. Это может быть и 0314 кВт•ч и 10314 кВт•ч и
20314 кВт•ч, так как счетчик показывает остаток
от деления израсходованного числа
киловатт-часов на 10 000.

Таких примеров можно привести
множество. Иногда найти остаток совсем нетрудно.
А как, например, найти остаток от деления числа
1996•1997•1998•1999•2000•2001 на 7? Перемножить и
разделить? Представьте себе проблемы, с которыми
придется столкнуться.

Эту задачу мы решим немного
позже и почти устно, познакомившись с теорией
«Арифметика остатков» или «Арифметика
сравнений».

Определение. Делитель в
теории чисел называется модулем, а числа, дающие
при делении на модуль одинаковые остатки,
называются сравнимыми по модулю.

Например, 8 = 7•1 + 1, 15 = 7•2 + 1.
Числа 8 и 15 при делении на 7 дают одинаковые
остатки, равные 1, следовательно, 8 и 15 сравнимы по
модулю 7. Это записывают так: 15 є 8 (mod 7), аналогично 22 є 15 (mod 7).

В качестве модуля можно взять
любое натуральное число. Например, 20є5 (mod 3), 16є4 (mod 4), 37є7 (mod 10). 

Вообще aєb (mod m), если a = mc + r, b = mc + r, где 0 m r
< m.

Заметим, что если 15є8 (mod 7), то (15 –
7. Здесь значок обозначает «кратно» или
«делится на…».

Например, если 11є5 (mod 3), то (11 –
5) 3.

Вообще, если aєb (mod m), то a – b =
(mc + r) – (md + r) = m(c – d) m.

Мы доказали, что если числа
сравнимы по модулю m, то их разность делится на
модуль m.

Верно и обратное утверждение:
если разность двух чисел делится на m, по эти
числа сравнимы по модулю m.

В самом деле, если бы эти числа
не были сравнимы по модулю m, то давали бы разные
остатки при делении на m, но тогда их разность не
могла бы делиться на m. Это свойство сравнений мы
будем использовать, например, для доказательства
сравнимости чисел:

10є3 (mod 7), так как 10 – 3 = 7 7;
21є13 (mod 4),
так как 21 – 13 = 8 4.

Из этого свойства вытекает
способ получения сравнимых по модулю чисел:
прибавить или вычесть из данного числа кратные
модулю числа.

Например, 11є8є5є2 (mod 3). Причем, натуральное
число, меньшее модуля и сравнимое с другими
числами, служит остатком от деления этих чисел на
модуль. В рассмотренном примере остаток равен 2.

Приведем еще один пример: 23є19є15є11є7є3 (mod 4).

Здесь число 3 – остаток от
деления указанных чисел на 4.

 Действия над
сравнениями

1. Заметим, что

    10є3(mod 7)
+ 12є5(mod 7)

______________
   22є8(mod 7), 
                           
так как 22 – 8 = 14 7.

Вообще,

   aєb(mod m), т. е. (a – b) m
+ cєd(mod m),
т. е. (c – d) m
__________________________
a + cєb +
d(mod m),
                         
так как (a + c) – (b + d) = (a – b) + (c – d) m.

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

Задача 1. Найдите остаток от
деления суммы  1995 + 1996 + 1997 + 1998 + 1999 на 7.

Решение.

Так как 1995 = 7•285, то 1995є0 (mod 7), то
1995 + 1996 + 1997 + 1998 + 1999є0 + 1 + 2 + 3 + 4 = 10є3 (mod 7).

Остаток равен 3.

Задача 2. Найдите остаток от
деления:вашего года рождения, например 1988 г.,
на 11.

Имеем 1988 = 11•80 + 8, значит, 1998є8 (mod 11);
года рождения вашей мамы, например 1953 г., на 11.
Получаем

1953 = 11•177 + 6, значит 1953є6 (mod 11);

суммы годов рождений, вашего и
маминого, на 11. Находим 1988 + 1953є8 + 6 = 14є3 (mod 11).

2. Заметим, что

   10є3(mod 7)
• 12є5(mod
7)
______________
120є 8(mod 7),
              так
как 120 – 15 = 105 7.

Сравнения по одному и тому же
модулю, можно перемножать, следовательно, и
возводить в натуральную степень. (Это
утверждение для шестиклассников можно не
доказывать, только показать на примерах. Для
старшеклассников его следует доказать.)

Итак, пусть aєb (mod m) и cєd (mod m).

Докажем, что acєbd     (mod m).

Доказательство. Рассмотрим
разность

ac – bd = ac – bc + bc – bd = c(a – b) + b(c
– d) m,    так как (a – b) m и (c – d)
m.

Следовательно, acєbd (mod m), что и
требовалось доказать.

Задача 3. Найдите остаток от
деления на 7 произведения чисел
1995•1996•1997•1998•1999.

Решение. Так как 1995є0 (mod 7), то
1995•1996•1997•1998•1999 Ю 0•1•2•3•4 = 0 (mod 7).

Таким образом, остаток равен 0.

Задача 4. Найдите остаток от
деления на 7 числа 1996•1997•1998•1999•2000•2001.

Решение. Имеем  
1996•1997•1998•1999•2000•2001є 1•2•3•4•5•6 = 720є20є6 (mod 7).

Остаток равен 7.

Часто встречаются
произведения вида 1•2•3•4, 1•2•3•4•5, 1•2•3•4•5•6
и т д.

Их обозначают 1•2•3•4 = 4!,
1•2•3•4•5 = 5!. Читают: 4-факториал, 5-факториал и
т. д. Вообще, 1•2•3•…•n = n! (n-факториал).

(Найдите самостоятельно
значения выражений 5!, 7!.)

Заметим, что остаток от
деления числа на 10 есть последняя цифра этого
числа.

Пример. 21є1 (mod 10), 134є4 (mod 10).

Для решения ряда задач на
поиски последней цифры числа полезна следующая
«таблица», которую следует вывести вместе с
учащимися:

1kє1 (mod 10) 42kє6 (mod 10) 24kє6 (mod 10) 24k+1є2 (mod 10) 24k+2є4 (mod 10) 24k+3є8 (mod 10)

5kє5 (mod 10) 42k+1є4 (mod 10) 34kє1 (mod 10) 34k+1є3 (mod 10) 34k+2є9 (mod 10) 34k+3є7 (mod 10)

6kє 6 (mod 10) 92kє 1 (mod 10) 74kє1 (mod 10) 74k+1є 7 (mod 10) 74k+2є 9 (mod 10) 74k+3є3 (mod 10)

92k+1є9 (mod 10) 84kє6 (mod 10) 84k+1є8 (mod 10) 84k+2є4 (mod 10) 84k+3є2 (mod 10)

  Вывод этих сравнений
можно показать на примере:

7є7 (mod 10);
7² = 49є9 (mod 10);
7³ = 7²•7є9•7 = 63є3 (mod 10);
7⁴ = 7³•7є3•7 = 21є1 (mod 10).

Далее остатки будут
повторяться: остаток 1 имеют все степени числа 7,
показатель которых кратен 4; остаток 7 – все
степени 7, показатель которых при делении на 4
дает остаток 1; остаток 9 – все степени 7,
показатель которых при делении на 4 дает остаток
2; остаток 3 – все степени 7, показатель которых
при делении на 4 дает остаток 3.

Задача 5. Какова последняя
цифра числа 137100?

Решение. Имеем:  137є7 (mod 10), 137¹⁰⁰є 7¹⁰⁰ = 7^25•4є1 (mod 10).

Последняя цифра равна 1.

Задача 6. Найдите последнюю
цифру каждого из следующих чисел: 7⁷, 77⁷⁷,
2¹⁰⁰, 3¹⁹⁹⁹, 19¹⁰⁰, 1999¹⁹⁹⁹.

Решение. Получаем:  

7⁷ = 7^4•1+3є3 (mod 10),
77⁷⁷є7⁷⁷ = 7^4•19+1є7 (mod 10),
2¹⁰⁰ = 2^4•25є6 (mod 10),
3¹⁹⁹⁹ = 3^4•499+3є7 (mod 10),
19¹⁰⁰ є9¹⁰⁰є1 (mod 10).
1999¹⁹⁹⁹є9¹⁹⁹⁹є9 (mod 10).

Последняя цифра
соответственно 3, 7, 6, 7, 1, 9.

Задача 7.

а) Найдите остаток от деления
на 3 числа 1998¹⁹⁹⁸ + 1999¹⁹⁹⁹.
б) Найдите последнюю цифру числа 1998¹⁹⁹⁸ + 1999¹⁹⁹⁹.

Решение.

а) 1998¹⁹⁹⁸ + 1999¹⁹⁹⁹є0¹⁹⁹⁸ + 1¹⁹⁹⁹
= 0 + 1є1 (mod 3).  
Остаток равен 1.
б) 1998¹⁹⁹⁸ + 1999¹⁹⁹⁹є8¹⁹⁹⁸ + 9¹⁹⁹⁹ = 8^4•499+2 + 9^2•999+1є4 + 9 = 13є3 (mod 10).

Последняя цифра равна 3.

Рассмотрим еще ряд задач,
решаемых арифметикой сравнений.

Задача 8. Докажите, что n³
– n кратно 6 для любого натурального числа n.

Решение. Истинность
утверждения для некоторых n еще не служит
доказательством. Рассмотрим для ясности
несколько частных случаев. Например,

при n = 1        
1³ – 1 = 0 6,
при n = 2        2³ – 2 = 8 – 2 = 6
6,
при n = 10      10³ – 10 = 1000 – 10 = 9906.

Теперь докажем утверждение
задачи. При делении на число 6 возможны следующие
остатки: 0, 1, 2, 3, 4, 5.

Тогда если

nє0 (mod 6), то  n³ – n = 0³
– 0 = 0 (mod 6),
nє1 (mod 6),
то  n³ – n = 1³ – 1 = 0 (mod 6),
nє2 (mod 6),
то  n³ – n = 2³ – 2 = 6є0 (mod 6),
nє3 (mod 6),
то  n³ – n = 3³ – 3 = 24є0 (mod 6),
nє4 (mod 6),
то  n³ – n = 4³ – 4 = 60є0 (mod 6),
nє5 (mod 6),
то  n³ – n = 5³ – 5 = 120є0 (mod 6).

Полный перебор показал, что n³
– n кратно 6 для любого натурального числа n.

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

Задача 9. Укажите все
возможные остатки при делении чисел вида n²
+ 3n на 7.

Решение. При делении на 7
возможны остатки 0, 1, 2, 3, 4, 5, 6. Тогда:

nє0 (mod 7),   n² + 3n = 0²
+ 3•0 = 0 (mod 7),
nє1 (mod 7),  
n² + 3n = 1² + 3•1 = 4 (mod 7),
nє2 (mod 7),  
n² + 3n = 2² + 3•2 = 10є3 (mod 7),
nє3 (mod 7),  
n² + 3n = 3² + 3•3 = 18є4 (mod 7),
nє4 (mod 7),  
n² + 3n = 4² + 3•4 = 16 + 12 = 28є0 (mod 7),
nє5 (mod 7),  
n² + 3n = 5² + 3•5 = 25 + 15 = 40є5 (mod 7),
nє6 (mod 7),  
n2 + 3n = 6² + 3•6 = 36 + 18 = 54є5 (mod 7).

Возможные остатки: 0, 3, 4, 5.

В качестве самостоятельной
тренировочной или домашней работы следует
предложить упражнения следующего типа:

1. Найдите последнюю цифру
числа:

а) 11⁶ + 14⁶ + 16⁶;
б) 11•13•15•17•19.

2. Найдите остаток от деления
на 4 числа:

а) 11⁶ + 14⁶ + 16⁶;
б) 11•13•15•17•19.

3. Докажите, что n³ + 2n
кратно 3 для любого натурального значения n.

Решения.  

1.

а) 11⁶ + 14⁶ + 16⁶є1⁶ + 4⁶
+ 6⁶є1 + 6 + 6 = 13є3 (mod 10);
б) 11•13•15•17•19 = 1•3•5•7•9є5 (mod 10).

2.

а) 11⁶ + 14⁶ + 16⁶є3⁶ + 2⁶
+ 0⁶ =3⁴•3² + 64є1•9 + 0 = 9є1 (mod 4);
б) 11•13•15•17•19є3•1•3•1•3 = 27є3 (mod 4).

3.

nє0 (mod 3), n³ + 2nє0³ + 2•0є0 (mod 3),
nє1 (mod 3),
n³ + 2nє1³ + 2•1 = 3є0 (mod 3),
nє2 (mod 3),
n³ + 2nє2³ + 2•2 = 8 + 4 = 12є0 (mod 3).

Следовательно, n³ + 2n
кратно 3 для любого натурального значения n.

Проверку усвоения материала
рекомендуется провести следующим образом.
Ученики выполняют задания и каждую цифру ответа
заменяют буквой, используя таблицу шифра. Если
ученик справится с заданием, то в четвертом
столбце заполненной таблицы он прочитает слово
«верно».

Таблица шифра

Вариант 1 Вариант 2

Укажите последнюю
цифру числа:

Найдите остаток от
деления:

Ученики сдают свои листки с
ответами и, пока учитель просматривает их, они
выполняют следующее задание.

Вариант 1

Найдите остаток от деления на
9 числа 1998¹⁹⁹⁹ + 1999¹⁹⁹⁸.

Делится ли это число на 3? Если
нет, то какой остаток дает при делении на 3?

Вариант 2

Найдите последнюю цифру числа
  1998¹⁹⁹⁹ + 1999¹⁹⁹⁸.

Делится ли это число на 5? на 2?

Несколько задач,
объединенных общей идеей

1. Докажите, что n(n + 1)
2.

Способ I.

nє0 (mod 2), n(n + 1)є0(0 + 1) = 0 (mod 2);
nє1 (mod 2),
n(n + 1)є1(1 +
1) = 2є2 (mod 2).

Способ II. Из двух
последовательных чисел n и (n + 1) одно всегда четно,
следовательно, их произведение n(n+1) четно.

2. Докажите, что n(n + 1)(n + 2) 3.

Двое учащихся по очереди
проговаривают доказательство показанными выше
способами. Учитель предлагает классу составить
аналогичные задачи. Ученики формулируют задачи.

Докажите, что

n(n + 1)(n + 2)(n + 3) 4;
n(n + 1)(n + 2)(n + 3)(n + 4) 5;
n(n + 1)(n + 2)(n + 3)(n + 4)(n + 5) 6.

Затем обобщают задачу: n(n + 1)(n +
2)…(n + m) (m + 1).

Вернемся к выражению n(n + 1)(n + 2).
Здесь n(n + 1) 2 и n(n + 1)(n + 2) 3,

2 и 3 – взаимно простые числа,
значит, n(n + 1)(n + 2) 1•2•3 = 3! = 6.

Докажем, что n(n + 1)(n + 2)(n + 3)
4! = 24.

Способ I. Нужно рассмотреть 24
случая сравнений, так как при делении числа на 24
возможны следующие остатки: 0, 1, 2, …, 24. Их
количество можно уменьшить, так как 24 = 3•8, а 3 и 8
– взаимно простые числа. Таким образом, можно
рассмотреть только 3 + 8 = 11 сравнений, три из
которых – сравнения по модулю 3 и восемь – по
модулю 8.

Способ II. Выше было доказано,
что n(n + 1)(n + 2) 3. Среди четырех последовательных
чисел n, n + 1, n + 2, n + 3 два четных. Докажем, что если
одно из них делится на 2, то другое делится на 4.
Эти числа имеют вид 2k и 2(k + 1). Из чисел k и k + 1 одно
четное вида 2m, тогда 2•2m = 4m 4. Таким образом,
n(n + 1)(n + 2)(n + 3) 1•2•3•4 = 4! = 24.

Теперь можно доказать и
следующие утверждения:

n(n + 1)(n + 2)(n + 4) 5!;
n(n + 1)(n + 2)(n + 3)(n + 4)(n + 5) 6!.

Задание на дом

1. Найдите последнюю цифру
суммы:

а) 1² + 2² + … + 10²;
     
б) 1² + 2² + … + 100².

2. Докажите, что:

а) n² + n2;
б) n² – n2.

3. Докажите, что квадрат
нечетного числа при делении на 8 дает остаток 1.

4. Докажите, что сумма
квадратов двух последовательных натуральных
чисел при решении на 4 дает остаток 1.

Решения.

 1.

а) 1² + 2² + 3² + 4²
+ 5² + 6² + 7² + 8² + 9² + 10²
= 1 + 4 + 9 + 16 + 25 + 36 + 49 + 64 + 81 + 100є
є1 + 4 +  9 + 6
+ 5 + 6 + 9 + 4 + 1 + 0 = 45є5 (mod 10). Последняя цифра 5.
б) 1² + 2² + .. + 100²є5•10 = 50є100 (mod 10).
Последняя цифра 0.

2.

а) nє0 (mod 2), n² + nє0² + 0 = (mod 2), nє1 (mod 2), n²
+ nє1²
+ 1 = 2є0 (mod 2).
б) Доказывается аналогично.

3. Докажем, что (2n + 1)²є1 (mod 8).
Имеем: 

nє0 (mod 8), (2•0 + 1)² = 1є1 (mod 8),
nє1 (mod 8),
(2•1 + 1)² = 9є1 (mod 8),
nє2 (mod 8),
(2•2 + 1)² = 25є1 (mod 8),
nє3 (mod 8),
(2•3 + 1)² = 49є1 (mod 8),
nє4 (mod 8),
(2•4 + 1)² = 81є1 (mod 8),
nє5 (mod 8),
(2•5 + 1)² = 121є1 (mod 8),
nє6 (mod 8),
(2•6 + 1)² = 169є1 (mod 8),
nє7 (mod 8),
(2•7 + 1)² = 225є1 (mod 8).

4. Доказывается аналогично.

Литература

1. Генкин С.А., Итенберг И.В.,
Фомин Д.В. Математический кружок. Первый год. –
С.-Петербург, 1992.
2. Гусев В.А., Орлов А.И., Розенталь А.Л. Внеклассная
работа по математике в 6–8 классах. – М.,
Просвещение, 1997.
3. Иванов С.Г. Нестандартные задачи по алгебре, 5–7
классы. – С.-Петербург, Институт продуктивного
обучения, центр профессионального обновления
«Информатизация образования», 1999.

МБОУ Средняя общеобразовательная школа №7

Исследовательская работа по теме:

«Арифметика остатков»

Выполнил:

 Луцев Андрей Романович,

ученик 7А класса

МБОУ СОШ №7

г. Сальск

Руководитель:

Устимова Нина Владимировна,

учитель математики МБОУ СОШ №7 г. Сальска

                                                                Сальск, 2012

Содержание

1. Введение.

1. Основная часть.

1. Практическая часть.

1. Заключение.

1. Литература.

Введение

Решая олимпиадные задачи  на делимость чисел, я столкнулся с проблемой:

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

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

Для этого мне нужно было решить следующие задачи:

1. Установить факт существования простого способа решения сложных олимпиадных задач на делимость чисел.
2. Если этот способ существует, найти его.

Математика для всех нас начинается с целых чисел. Всюду – дома, в школе, в магазине, в троллейбусе или автобусе – мы складываем, умножаем, делим целые числа. Иногда разделить нацело нельзя – получается остаток, и многое зависит от того, каков этот остаток. Такие случаи я и рассматриваю в своей работе «Арифметика остатков» или арифметика сравнений. «Арифметика остатков» — одна из глав высшей арифметики, имеет отношение и к элементарной арифметике. Многие вопросы элементарной арифметики связаны с этой темой: и деление с остатком, и признаки делимости, и отыскание наибольшего общего делителя, и многое другое. Но эта тема имеет и самостоятельную ценность – арифметика сравнений представляет собой простой пример «необычной», «экзотической» арифметики, в которой действуют сложение и умножение, возведение в степень, вычитание и деление, подчиняющиеся тем же законам, что и в обычной арифметике. Необычность ее в том, что в ней имеется лишь конечное число не равных друг другу или несравнимых друг с другом чисел.

 На основе сказанного выдвинута гипотеза: существует наиболее рациональный способ нахождения остатков при делении больших чисел на натуральное число.

Основная часть

Со скоростью ЭВМ.

Каков будет остаток от деления числа 7778*7779*7780*7781*7782*7783 на 7?

 Для решения этой задачи нам не потребуется ЭВМ. Каждый научится решать такие задачи в уме. Надо только знать немного арифметику, но не обычную, которую в школе учат, а так называемую «арифметику остатков» или «арифметику сравнений». Так называется глава серьёзной математической науки – «теории чисел».

Сравнение целых чисел по модулю.

С арифметикой остатков мы сталкиваемся буквально на каждом шагу. Вот несколько примеров.

Пример 1. В коридоре висит счетчик. Взглянем на него. Он показывает, предположим, 0729 киловатт-часов. А на самом деле сколько электроэнергии израсходовано с момента установки счетчика? 729 кВт . ч? Или 10729? Или, может быть 30729? По показанию счетчика этого не скажешь. Ведь после 9999 на счетчике будет 0000, и счет начнется сначала. Счетчик так задуман, что указывает не полный расход энергии, а только остаток от деления израсходованного числа киловатт-часов на 10000.

Пример 2. Когда мы пошли в школу, на часах было ровно 8, а когда ложились спать, часы показывали 10, а 10 – 8 = 2. Но разве прошло 2 часа с того момента, как мы ушли в школу? Нет, не 2, а целых 14. Дело в том, что стрелки, дойдя до 12.00, каждый раз начинают отсчет времени заново, с нуля. Часы нам показывают не полное время, прошедшее с момента, когда они показывали 0.00, а лишь остаток от деления его на 12.

Можно еще много привести примеров и задач, в которых основную роль играет не частное от деления одного целого числа на другое, а остаток. Для решения такого вида задач была создана «арифметика остатков». Познакомимся с ней поближе.

Рассмотрим остатки от деления на 7. Делитель в теории чисел называется «модулем», а числа, дающие при делении на модуль 7 одинаковые остатки, называются «равноостаточными» или «сравнимыми по модулю 7». Два числа а и b при делении на некоторый модуль m дают одинаковые остатки, т.е. сравнимы по модулю m, записывается так:

                        .

Рассмотрим следующую таблицу:

  Эта таблица построена следующим образом: все целые числа выписаны подряд построчно, по семь чисел в каждой строке. Поэтому соседние числа одного столбца отличаются на 7, а значит при делении на 7 будут давать одинаковые остатки. В первом столбце оказались числа, делящиеся на 7 без остатка, во втором – дают при делении на 7 остаток 1 и т.д.  Известно, что при делении на m, образуется m различных видов остатков: 0, 1, 2, …, m – 1. Остатки в таблице выделены жирным шрифтом – это верхние числа каждого столбца. Можно сказать, что в один столбец попали те и только те числа, которые при делении на 7 равноостаточны, т.е. сравнимы по модулю 7. Итак, все числа разбились на 7 классов: в класс с индексом 0 попали числа, которые при делении на 7 дают в остатке 0 (делятся на 7 без остатка), в класс с индексом 1 – числа, дающие при делении на 7 в остатке 1, и т.д.

Правило определения класса. Чтобы узнать, в каком классе находится некоторое число, надо найти остаток от деления этого числа на m. Этот остаток равен индексу класса. 

    Если разность двух чисел делится на 7 без остатка, то оба числа попадают в один столбец, в один класс. Делаем выводы.

Вывод 1. В один класс попадают все числа, дающие при делении на модуль один и тот же остаток.

Вывод 2. Два числа принадлежат к одному и тому же классу тогда и только тогда, когда их разность делится без остатка на модуль.

Вывод 3. Остаток от деления суммы на модуль не изменится, если одно из слагаемых или каждое слагаемое заменить другим числом того же класса (в частности, индексом того же класса). В буквенном виде это свойство можно записать так:

если  и , то , т.е. сравнения можно складывать.

Вывод 4.  Остаток от деления произведения нескольких чисел на модуль М не изменится, если один из сомножителей ( или даже каждый из сомножителей)  заменить числом того же класса.

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

,

,

,

.

Практическая часть

Пример 1. Не проводя обычных вычислений, найти остаток от деления на 7 следующей суммы:      8+79+780+7781+77782+777783.

Решение: остатки от деления слагаемых на 7 равны 1,2,3,4,5,6; например, 77782=77777+5, а 777783=777777+6, значит индексы классов, в которых находятся слагаемые, равны 1,2,3,4,5,6.

Воспользуемся выводом третьим и заменим в данной сумме каждое слагаемое индексом его класса – индекс суммы от этого не изменится. Остаётся найти остаток от деления суммы   на 7

1+2+3+4+5+6=21

Эта сумма делится на 7 без остатка, значит, и данная в условии сумма делится на 7 без остатка.

Используя обозначения, можно решение этой задачи записать так:

8 ≡ 1(mod 7), 79 ≡ 2(mod 7), 780 ≡3(mod 7), 7781 ≡4(mod 7), 77782 ≡5(mod 7), 777783 ≡6(mod 7) ,

8+79+780+7781+77782+777783 ≡ 1+2+3+4+5+6 = 21 ≡ 0    (mod 7)

Ответ: сумма делится на 7 без остатка.

Теперь мы уже можем попытаться решить задачу, с которой начали:

 «Со скоростью ЭВМ».

Каков будет остаток от деления числа 7778*7779*7780*7781*7782*7783 на 7?

 Вместо суммы здесь стоит произведение.  Посмотрим, не обладает ли произведение таким же свойством, что и сумма.

Рассмотрим произведение нескольких, скажем, трех чисел: А, В и С.

Что произойдёт если в произведении АВС число А заменить другим числом того же класса А1? Так как А1 отличается от А на число, кратное 7, то А1=А+7К, где К – некоторое  целое число.

Значит, А1ВС = (А+7К) ВС = АВС+7КВС.

Отсюда видно, что АВС и А1ВС принадлежат к одному классу (отличаются на число кратное 7) .

   Мы можем заменить каждое число индексом его класса. Пользуясь обозначениями теории чисел, можно записать:

если  А ≡ В (mod M), C ≡ D (mod M),то AC ≡ BD (mod M),

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

Теперь нам не трудно решить первую задачу (со скоростью ЭВМ).

 Остаток не изменится, если мы все сомножители заменим индексами их классов, равными 1,2,3,4,5 и 6 соответственно.

Так как 1*2*3*4*5*6 =720 = 20 ≡ 6 (mod 7),

Ответ:  искомый остаток равен 6.

Все наши рассуждения применимы и в том случае, когда вместо модуля 7 используется любое другое натуральное число М, отличное от единицы. В этом случае, вместо таблицы из семи столбцов придётся рассматривать таблицу, содержащую М столбцов.

Пример 2. Доказать, что 776776 + 777777 + 778778 не делится на 3.

Решение: воспользуемся арифметикой вычетов по модулю 3. Так как 776 ≡ 2 (mod 3), то 7762 ≡ 4 ≡ 1 (mod 3), а 776776=  (7762)388 ≡1388 ≡ 1 (mod 3).

 778 ≡ 1 (mod 3) и 778778 ≡ 1778 ≡ 1 (mod 3).

 777 ≡ 0 (mod 3) и 777777 ≡ 0 (mod 3).

Складывая эти сравнения, получим: 776776 + 777777 + 778778 ≡ 1 + 0 + 1 ≡ 2 (mod 3), т.е. данная сумма даёт при делении на 3 остаток, равный 2.

Пример 3. Задача из учебника «Алгебра и начала анализа»10класс под редакцией Ю.М.Колягина. Найти остаток от деления 3946 на 5.

Решение: 39 = 4 (mod 5), 3946 = 446 (mod 5)

Выпишем степени 4: 41 = 4  42 = 16  43 = 64, т.е. 4 в нечётной степени, 6 в чётной степени. Число 46- чётное, значит последняя цифра  446 равна 6. 6 ≡ 1 (mod 5).

Ответ: остаток 1.

Пример 4.

В некотором месяце 3 четверга пришлись на четные числа.

Какой день недели был 26 числа этого месяца?

Решение:

В месяце 3 четных четверга, значит всего 5 четвергов т.к. в неделе 7 дней, то четверги чередуются: четный и нечетный.

Первый четверг – может быть 1,2 или 3 числом, если в месяце 31 день, и 1или 2 числом если в месяце 30 дней.

Значит: Первый четверг – 2 число, а Пятый четверг: 30, следовательно 26 число – это воскресенье.

Ответ: 26 число – это воскресенье.

Заключение.

Изучив «Арифметику остатков», я теперь легко решаю многие олимпиадные задачи на делимость чисел.

Литература.

В своей работе я использовал информацию из книг:

Гусев В.А., Орлов А.И., Розенталь А.Л. Внеклассная работа по математике. Москва, «Просвещение»,1984.

Фарков А.В., математические олимпиады в школе. М.,«Просвещение»,2011.

Колягин Ю.М., учебник «Алгебра и начало анализа», 10 класс.

Тезисы.

Тема: «Арифметика остатков».

Автор работы: ученик 7 «А» класса МОУ СОШ №7 Луцев Андрей Романович.

Руководитель: Устимова Нина Владимировна.

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

Задача:

1. Установить факт существования рационального способа решения сложных олимпиадных задач на делимость чисел.
2. В случае положительного ответа – поиск этого способа, предоставляющего лёгкое и быстрое нахождение решения олимпиадных задач, не выполняя громоздких вычислений.

В ходе работы выявлено:

1. С помощью «арифметики остатков» можно легко решать разные сложные задачи.

Вывод 1. В один класс попадают все числа, дающие при делении на модуль один и тот же остаток.

Вывод 2. Два числа принадлежат к одному и тому же классу тогда и только тогда, когда их разность делится без остатка на модуль.

Вывод 3. Остаток от деления суммы на модуль не изменится, если одно из слагаемых или каждое слагаемое заменить другим числом того же класса.

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

Пример 2.

В месяце 5 четвергов, так как четверги чередуются по четности и не четности.

30 дней – 1,2 четверг.  31 день -1,2,3 четверг

7*4+2=30 – 5 четверг.  29 – среда   26 – воскресенье.

Заключение.

Изучив «Арифметику остатков», я теперь легко решаю многие олимпиадные задачи на делимость чисел.