WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«Издательство МЦНМО ISBN: 978-5-4439-1126-7 Год издания: 2017 Тираж: 3000 экз. Количество страниц: 80 Размер: 145x200/4 Шестнадцатая книжка серии «Школьные математические ...»

Азы теории чисел

Автор: К.А.Кноп

Издательство МЦНМО

ISBN: 978-5-4439-1126-7

Год издания: 2017

Тираж: 3000 экз .

Количество страниц: 80

Размер: 145x200/4

Шестнадцатая книжка серии «Школьные математические кружки» посвящена арифметике

остатков. В неё вошли разработки семи занятий математического кружка для 7-9 классов с

подробно разобранными примерами различной сложности, задачами для самостоятельного

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

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

Рассматриваются теорема Вильсона, свойства функции Эйлера, китайская теорема об остатках, малая теорема Ферма и теорема Эйлера. Последние два занятия посвящены новым для кружков темам: псевдопростым числам и криптографии с открытым ключом. Каждое занятие проиллюстровано портретом и биографией автора теоремы. Для удобства использования заключительная часть книжки, как всегда, сделана в виде раздаточных материалов. Книжка адресована школьным учителям математики и руководителям математических кружков. Надеемся, что она будет интересна школьникам и их родителям, студентам педагогических вузов, а также всем любителям математики .



Оглавление

0. Предисловие

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

2. Решение сравнений. Теорема Вильсона

3. Леонард Эйлер и его функция

4. КТО–КТО в теремочке живёт

5. От Ферма к Эйлеру и обратно

6. Псевдопростые числа и числа Кармайкла

7. Шифрование с открытым ключом Предисловие Восьмым выпуском в серии «Школьные математические кружки» вышла книга А.И.Сгибнева «Делимость и простые числа» (в дальнейшем мы будем обозначать ее ДПЧ). В ней несколько первых занятий посвящены вопросам делимости натуральных чисел, рассказывается о свойствах деления (в том числе доказывается теорема об однозначности деления с остатком), а также о признаках делимости, но ничего не сказано об арифметике остатков (модулярной арифметике) – то есть о том математическом языке, появление которого в своё время произвело настоящую революцию в теории чисел — разделе математики, изучающем целые числа. Настоящая книжка является логическим продолжением ДПЧ, поэтому мы начинаем её с рассказа об этом языке. На следующих занятиях рассматриваются теорема Вильсона, свойства функции Эйлера, китайская теорема об остатках, малая теорема Ферма и теорема Эйлера. Все эти темы почти независимы друг от друга и могут изучаться в любом порядке .

Последние два занятия посвящены темам, которые для теории чисел являются относительно новыми (а для кружковых занятий – совсем новыми) – псевдопростым числам и криптографии с открытым ключом .

Все семь занятий предназначены для учеников 7–9 классов, хотя могут быть использованы и в кружках 10-11 классов .

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

.

Подавляющее большинство задач не новы. Многие из них встречалась в различных англоязычных учебниках по Elementary Number Theory. Автор выражает признательность А.С.Штерну и особенно А.В.Шаповалову, предложившим ряд ценных улучшений текста книги .



Говоря о числах и их делителях, мы подразумеваем целые числа и натуральные делители .

Буквами p и q, как правило, обозначены простые числа .

Кроме того, в книге содержится много ссылок на числовые последовательности из Онлайнэнциклопедии целочисленных последовательностей http://oeis.org. В качестве ссылок мы используем номера последовательностей в Онлайн-энциклопедии. Например, ссылка A000027 означает http://oeis.org/A000027 .

Занятие 1. Арифметика остатков Карл Фридрих Гаусс (30 апреля 1777 – 23 февраля 1855), немецкий математик, астроном и физик .

Ещё в детстве проявил яркие способности к математике и иностранным языкам. В 1796 году девятнадцатилетний Гаусс решил задачу, поставленную ещё Евклидом: он нашел способ построить с помощью циркуля и линейки правильный 17-угольник. В 24 года Гаусс опубликовал знаменитые «Арифметические исследования», в которых изложил теорию квадратичных вычетов и сравнений второй степени, а также доказал «квадратичный закон взаимности». Именно в «Арифметических исследованиях» впервые был применён современный язык сравнений, сделавший возможным работу с делимостью чисел как с равенствами. Все догауссовские способы записи фактов о делимости целых чисел были трудночитаемыми и потому неудобными .

В зрелом возрасте Гаусс активно занимался алгеброй, астрономией, геодезией, был избран иностранным членом многих академий наук, включая и Петербургскую. Его научные интересы были столь разносторонними, а вклад в математические науки столь весомым, что он по праву заслужил титул «короля математиков» .

Фотопортрет К. Гаусса сделан А.Виттманом в 1887 году .

Если m1 и (a–b) m, то говорят, что a и b сравнимы по модулю m. Сравнимость записывают так: a b (mod m). Если значение модуля очевидно из контекста, то скобки с указанием модуля обычно опускают .

Использование сравнений, то есть записи a b вместо делимости (a–b) m, оказывается очень удобным и мощным инструментом в разных задачах, потому что со сравнениями, как мы сейчас убедимся, можно действовать привычно, как с равенствами, то есть складывать, вычитать, умножать, иногда делить .

1.1. а) Докажите, что если a b (mod m) и c d (mod m), то a+c b+d (mod m);

б) Докажите, что если a b (mod m) и c d (mod m), то ac bd (mod m) .

Решение. а) (a+c) – (b+d) = (a–b) + (c–d). Так как каждая скобка в правой части равенства делится на m, то и их сумма (разность скобок в левой части равенства) кратна m. Это и означает, что a+c b+d .

б) ac – bd = a(c–d) + d(a–b). Из условий следует, что a–b m и c–d m, поэтому ac–bd m .

1.2. Докажите, что если a b (mod m) и k – натуральное число, то ak bk (mod m) .

Указание. Один способ доказательства – с помощью алгебраического тождества ak – bk = (a– b)(ak–1 + ak–2b + … +abk–2+ bk–1). Другой способ – с помощью математической индукции, многократно применяя произведение сравнений (задачу 1.1б) .





Мы будем говорить, что множество M образует полную систему остатков по модулю m, если для каждого целого числа существует ровно один сравнимый с ним (по модулю m) элемент этого множества. Чаще всего в качестве полной системы остатков выбирается множество {0, 1, 2,..., m–1} или множество {1, 2,..., m}, а для доказательства того, что какая-то система остатков является полной, для неё устанавливают взаимно однозначное соответствие с одним из двух указанных выше множеств .

Комментарий: в этом определении можно заменить условие единственности сравнимого элемента на условие |M|=m или даже на |M|m. Действительно, если для каждого целого числа есть хотя бы один сравнимый с ним элемент множества, и при этом общее количество элементов M не больше m, то двух различных элементов, сравнимых с одним и тем же числом, быть не может .

1.3. Пусть m – натуральное число. Докажите, что множество M={0, 3, 6,..., 3m–3} образует полную систему остатков тогда и только тогда, когда m .

Решение. Сначала докажем простую (почти очевидную) часть этого утверждения. Если m 3, то m M, потому что m 3m–3, а M содержит все числа, кратные 3 и не превосходящие 3m–

3. Но так как m 0 (mod m), то M содержит хотя бы два различных элемента, сравнимых с числом m (а именно, 0 и m). Следовательно, M не образует полной системы остатков .

Если же m, то m=3k+1 или m=3k+2 для некоторого натурального k. Разберем первый случай (второй рассматривается аналогично): M={0, 3, 6,..., 3k, 3k+3,..., 6k, 6k+3,..., 9k}. Все числа от 0 до 3k оставим на месте, а вместо чисел от 3k+3 до 6k выпишем числа, меньшие их на m (это сохраняет единственность сравнимого элемента множества): получатся числа 2, 5,..., 3k–1. Точно так же для чисел от 6k+3 до 9k выпишем вместо них числа, меньшие их на 2m=6k+2 – получатся числа 1, 4,..., 3k2. В итоге получились все числа от 0 до 3k (то есть до m–1), каждое число встречается ровно один раз. Следовательно, система остатков является полной .

1.4. Постройте таблицу умножения по mod 5 .

–  –  –

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

1) почему в первой таблице не было нулей, а во второй они есть?

2) почему в каждой строчке первой таблицы никакое число не повторяется дважды?

3) для каких модулей в пределах первого десятка таблицы умножения будут похожи на таблицу mod 5, а для каких — на таблицу mod 6?

4) сколько в таблице mod 12 таких строчек, в которых нет нулей?

Ответы на эти вопросы:

1) потому что 5 – простое число, а 6 – составное. Когда перемножаются два числа, одно из которых кратно 2, а другое кратно 3, то в результате (в таблице mod 6) получается 0 .

2) ровно по той же причине: если бы ab aс при разных b и c, то в той же строчке должен был быть 0: a(b–c) Но по простому модулю это невозможно .

3) по–видимому, для простых модулей (то есть чисел 2, 3, 7) таблицы будут аналогичны таблице mod 5 (нет нулей, все числа в каждом столбце и каждой строке различны), а для составных — аналогичны таблице mod 6 .

4) этот вопрос формулируется так: для каких множителей m12 не может выполняться равенство mn ни при каких n12? Невозможность такого равенства равносильна условию m 12. Иначе говоря, m=1, 5, 7 или 11. Ответ: 4 строчки .

Задачи к занятию 1 .

1.6. Найдите наименьшие неотрицательные остатки для 6k+1 (mod 17) при k=1,2,3,4,5 .

Решение. 61+1 = 7, 62+1 2+1=3 (mod 17).Дальше проще считать сразу «в остатках», учитывая предыдущие найденные остатки для степеней шестёрки, перемножая нужные из них и затем добавляя к результату 1: 63+1 = 64+1 =

1.7. а) Пусть m – нечётное натуральное число. Докажите, что множество {0, 2, 4, …, 2m–2} – полная система остатков по mod m. б) Пусть k m. Докажите, что множество {0, k, 2k, …, (m–1)k} – полная система остатков по mod m. в) Пусть k m, r – произвольное число .

Докажите, что {r, k+r, 2k+r, …, (m–1)k+r} – полная система остатков по mod m .

Указание. Решение всех пунктов аналогично второй части решения задачи 1.3 .

–  –  –

Решение. По условию, произведение d(a–b) m и d m. Следовательно, (a–b) m, а это и означает, что a b (mod m) .

1.9. Пусть d – натуральное число, являющееся общим делителем a, b и m. Докажите, что сравнения a b (mod m) и a/d b/d (mod m/d) равносильны .

Решение. Пусть a=da’, b=db’, m=dm’. Тогда первое сравнение эквивалентно условию (a–b) m, то есть (da’–db’) dm’, а второе сравнение эквивалентно (a’–b’) m’. Очевидно, что два таких сравнения равносильны друг другу .

1.10. Пусть p(x) – многочлен c целыми коэффициентами и a b (mod m). Тогда p(a) p(b) (mod m) .

Указание. Запишите многочлен в стандартном виде, после чего воспользуйтесь результатами задач 1.1 и 1.2 и методом математической индукции .

1.11. Докажите, что 72014 + 92014 10 .

Решение. Найдем несколько первых степеней семёрки по модулю 10: 71 =7, 72=499, 73=749793, 74731. Так как 2014=4503+2, то 72014=(74)50372 15039 9 (mod 10) .

Аналогично для степеней девятки: 92=81и поэтому 92014=(92)1007Следовательно, 72014+92014(mod 10) .

Комментарий. Совсем нетрудно убедиться, что степени натуральных чисел всегда «зацикливаются» (по любому модулю). Это следует из того, что количество различных остатков конечно, а так как количество натуральных степеней бесконечно, то какой–то остаток обязательно встретится второй раз. Дальше из свойства произведения сравнений следует, что все последующие остатки тоже будут повторены, т. е. возникнет цикл остатков .

В решении задачи мы фактически нашли такой цикл (и для семёрки, и для девятки) и воспользовались тем, что в нём есть остаток 1 .

1.12. Докажите, что ни при каком натуральном n число 3n + 5n не является точным квадратом .

Решение. Поначалу совершенно непонятно, какое отношение эта задача имеет к сравнениям по модулю. Поэтому начнём с того, что просто сосчитаем несколько первых чисел вида 3 n + 5n: 31+51=8, 32+52=34=217, 33+53=152=819, 34+54=706=2353, 35+55=3368=8421. Возникает гипотеза: при нечётных показателях степени 3n + 5n делится на 8, но не делится на 16, а при чётных — делится на 2, но не делится на 4. А так как все точные квадраты содержат чётную степень двойки, то выражение 3n + 5n не может быть точным квадратом. Осталось это доказать с помощью сравнений по модулю. Теперь уже понятно, что выбирать нужно модуль 16, чтобы получить по нему 8 для нечётных степеней и какие–то ещё не кратные 4 числа для чётных. Цикл для степеней 3 по модулю 16: 1, 3, 9, 11, 1. Цикл для степеней 5: 1, 5, 9, 13, 1 .

Оба цикла имеют длину 4, поэтому 3n + 5n тоже даёт цикл длины не более 4: 1+1=2, 3+5=8, 9+9 Выясняется, что длина этого цикла на самом деле равна 2, и он состоит только из двоек и восьмёрок, что и доказывает утверждение задачи .

1.13. Последовательность (an) задана формулами a1=a2=1, an+2=an an + 1 + 1. Докажите, что (an – 3) – составное число при n 5 .

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

a1=1, a2=1, a3=2, a4=3, a5=7, a6=22, a7=155, a8=3411, a9=528706. (A007660) Для a7 и a8 было очевидным то, что результат после вычитания 3 не будет простым числом: в результате получались чётные числа. Однако то, что 528703 не является простым, как минимум не очевидно. А дальше члены последовательности начинают расти так, что даже вычисление десятого члена без калькулятора уже затруднительно. Изюминка этой задачи состоит в том, что такие громоздкие вычисления вовсе не нужны! Достаточно того, что мы легко можем считать члены этой последовательности по модулю, равному одному из предыдущих членов: an+11 (mod an), an+21 (mod an), поэтому an+3 11+1 = 2 (mod an), an+4 21+1 = 3 (mod an), an+5 32+1 = 7 (mod an)... Этого уже хватает, и даже с запасом: так как an+4 3 (mod an), то (an+4 – 3) an, причем an1. А значит, an+4 – 3 является составным числом .

Дополнительные задачи к занятию 1 Д1.14. Пусть m=2s+1 – нечётное натуральное число. Докажите, что множество {–s, 1–s, …, – 1, 0, 1, …, s–1, s} – полная система остатков по mod m .

Указание. Добавьте по m=2s+1 ко всем отрицательным элементам множества .

Д1.15. Докажите, что {0, 1, 2, 22,..., 29} – полная система остатков по mod 11 .

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

Д1.16. С помощью утверждения задачи 1.10 докажите признаки делимости на а) 9; б) 11 .

Решение. а) Десятичную запись натурального числа можно рассматривать как значение многочлена с целыми коэффициентами в точке a=10. При этом сумма цифр числа – это значение того же многочлена в точке b=1. Так как 101 (mod 9), то из 1.11 получаем утверждение о том, что каждое число сравнимо со своей суммой цифр по модулю 9 – а это и есть обобщённый признак делимости на 9 1 .

б) знакочередующаяся сумма цифр (–1)n an +(–1)n–1 an–1 + a0 – это значение этого же самого многочлена в точке b=–1. Так как 10 –1 (mod 11), то из 1.11 получаем утверждение о том, что каждое число сравнимо со своей знакочередующейся суммой цифр по модулю 11 .

Д1.17. Пусть x, y, z – целые числа, удовлетворяющие уравнению x2+y2=z2. Докажите, что xyz (mod 60) .

Решение. Рассмотрите отдельно делимость xyz на 3, 4 и 5. Например, рассуждение по mod 5 может быть таким: если ни x, ни y не делятся на 5, то их квадраты при делении на 5 дают Точнее говоря, это признак равноостаточности по модулю 9 .

остатки 1 или 4. Тогда x2+y2 даёт остаток 1+1, 1+4 или 4+4. Из трёх этих вариантов квадратом может быть только 1+4 0, то есть z делится на 5, откуда сразу получаем, что xyz делится на 5 .

Д1.18. Найдите остатки от деления 1002015 на а) 99; б) 101; в) 9999 .

Решение. а) 100 1 (mod 99), поэтому 1002015 12015 1 (mod 99) б) 100 –1 (mod 101), поэтому 1002015 (–1)2015 –1 (mod 101) .

Обратите внимание на то, как сравнение с отрицательным числом –1 избавило от выполнения умножений .

в) 1002015 = (1002)1007 1001 = 100001007 100 11007 100 100 (mod 9999) Комментарий: подумайте, как вывести в) из результатов а) и б) .

Д1.19. Найдите остаток от деления 20112012201320142015 а) на 2010 б) на 2016 .

Решение. а) Заменим каждое число его остатком. По свойству произведения сравнений получим 20112012201320142015 12345 = 120 (mod 2010). Так как 0 120 2010, оно и является остатком от деления произведения шести указанных чисел на 2010 .

б) Здесь удобнее заменить каждое число сравнимым с ним отрицательным числом. Тогда по свойству произведения получим 20112012201320142015 (–5)(–4)(–3)(–2)(–1) = –120 (mod 2016). Поэтому искомым остатком будет число 2016 – 120 = 1896 .

Д1.20. Докажите, что если 2n – 1 11, то 2n – 1 93 .

Решение. Здесь снова помогает рассмотрение циклов. По модулю 11: 20=1, 21=2, 22=4, 23=8, 24=16 Далее остатки повторяются, поэтому мы делаем вывод о делимости 2n – 1 на 11: 2n – 1 (mod 11) n

10. Число 93 не простое, поэтому лучше рассмотреть его простые делители 3 и 31. По модулю 31: 20=1, 21=2, 22=4, 23=8, 24=16 и делается аналогичный вывод: 2n – 1 (mod 31) n 5. По модулю 3 всё ещё проще: любая чётная степень двойки сравнима с 1 .

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

Д1.21. Докажите, что 2100 и 3100 сравнимы а) по модулю 5, б) по модулю 13 .

в) Найдите еще хотя бы один простой модуль, по которому эти числа также сравнимы .

Решение. а) Здесь тоже можно было бы поступить аналогично решению задач 1.6, 1.11, Д1.20 и сосчитать несколько первых остатков (до зацикливания), но мы покажем более простой способ. Из сравнения 3 –2 (mod 5) следует, что 3100 (–2)100 = (–1)1002100 2100 (mod 5) .

б) Аналогично, 32 = 9 = –4 = –22 (mod 13). Отсюда 3100 (–22)50 (mod 13)

в) Решение задач а) и б) наводит на идею поискать такое простое p, которое равно 3d+2d для некоторого d, являющегося делителем числа 100. На первый взгляд, годится d=4 и p=34+24=97, однако тогда 3100=(34)25 = (–24)25 = –2100 (mod 97), а не 2100 (mod 97). В чем причина неудачи? Очевидно, мешает нечётность числа 100/4=25. Пробуем следующий делитель: d=5, но число 35+25=275 не простое. Зато оно содержит простой множитель 11, поэтому 3100=(35)20 = (–25)20 = 2100 (mod 11) .

Комментарий: Другой вариант – рассмотреть делимость на p=35–25=211 .

Д1.22. Докажите, что (3n – 1)n – 4 3n–4 при любом натуральном n .

Решение. 3n – 1 (mod 3n – 4). Поэтому (3n – 1)n – 4 3n – 4 (mod 3n – 4) .

Д1.23. Найдите все нечётные натуральные делители числа 52n + 325n–2 .

Решение. 52n + 325n–2 = 2525n–2+ 325n–2 = 2825n–2 n. Нечётными делителями такого числа являются только 1 и 7 .

Д1.24. Докажите, что а) 3n+2 + 42n+1 13. б) 6n+2 + 72n+1 43. в) kn+2 + (k+1)2n+1 k2+k+1 Решение. а) 3n+2 + 42n+1 = 93n + 4n (9+4)3n 0 (mod 13)

б) как и а), является частным случаем задачи в) .

в) kn+2 + (k+1)2n+1 = k2kn+(k+1)(k2+2k+1)n k2kn+(k+1)kn = (k2+k+1) kn 0 (mod k2+k+1) .

Д1.25. Докажите, что 25n+1 + 5n+2 27 .

Указание. Воспользуйтесь тем, что 32 5 (mod 27) и 2+25 0 (mod 27) .

Д1.26. Докажите, что если a – нечётное число, а n – натуральное, то a2^n 1 (mod 2n+2) .

Указание. Воспользуйтесь методом математической индукции. Базу индукции (n=1) доказать нетрудно: (a–1) и (a+1) – два последовательных чётных числа, поэтому одно из них кратно 4, а значит, их произведение кратно 8 .

Д1.27. Число a заканчивается на 33. На какие две цифры заканчивается a85 ?

Указание: умножать число 33 на себя 85 раз — не лучшая идея, и искать цикл по mod 100 тоже не нужно. Собственно, смысл этого упражнения как раз в том, чтобы придумать, как обойтись сравнительно небольшим числом умножений .

–  –  –

Комментарий 1: Нам хватило всего 8 умножений, а цикл имеет длину 20, поэтому если бы досчитывать все степени подряд до появления цикла, то вычислительной работы было бы больше .

Комментарий 2: Набор промежуточных степеней вместо у нас был таким: 2, 4, 8, 16, 17, 34,

68. Иначе говоря, мы нашли сначала 17 – наибольший простой делитель 85, а затем вычисляли его квадрат и четвёртую степень. Можно было бы пойти и через другой простой делитель, то есть вычислить 2, 4, 5, 10, 20, 40, 80 степени и затем уже использовать 85 = 80+5. Это дало бы результат за те же 8 умножений .

Решение 2. Будем последовательно возводить числа в квадрат, увеличивая найденную степень вдвое .

Вплоть до a16 мы это уже сделали в решении 1, далее a32 8181 61 (mod 100), a64 6161 21 (mod 100). Теперь осталось перемножить нужные степени a: a85 = a a4 a16 a64 33 21 81 21 93 (mod 100) Комментарий 3. Решение 2 требует 9 умножений, то есть менее экономно. Зато оно более универсально, так как позволяет вычислить результат для любой степени, не раскладывая ее на множители, а воспользовавшись двоичной записью. Впрочем, достаточно часто такой способ является одновременно и самым экономным. Последовательность A003313 перечисляет минимальное число умножений, требуемых для возведения в n-ю степень, а A014701 — количество умножений, требуемых для возведения в степень «двоичным»

методом (как в решении 2). Среди 50 первых значений этих двух последовательностей 40 значений совпадают, и только для 10 значений n «двоичный» метод хуже оптимального (на одно умножение) .

Д1.28. Найдите три последних цифры числа 72016 .

Решение. 74 (mod 1000)поэтому 74n (1+400)n n. Так как 2016=4504, а 1+400504 = 601 (mod 1000), то 72016 заканчивается на 601 .

Д1.29. Найдите все значения n, для которых 1!+2!+...+n! – точный квадрат .

Решение. При n 4 точных квадратов нет. При n 5 1!+2!+3!+4! +... + n! 1!+2!+3!+4! 5 (mod 10), поэтому точным квадратом сумма может быть только если она заканчивается на 25 .

Но так как по модулю 4 сумма всех последующих факториалов равна 3, то заканчиваться на 25 она не может .

Д1.30. Пусть m – чётное число. Докажите, что если {a1, a2,..., am} и {b1, b2,..., bm} – две полных системы остатков по модулю m, то {a1+b1, a2+b2,..., am+bm} не является полной системой остатков по модулю m .

Решение. Предположим противное. Тогда 1+2+...+m (a1+b1)+(a2+b2)+...+(am+bm) = (a1+a2+.. .

+am) + (b1+b2+...+bm) 2(1+2+...+m) (mod m). Отсюда получается, что 1+2+...+m 0 (mod m), то есть m(m+1)/2 m, что невозможно при чётном m. Противоречие .

Д1.31. [Mосковская олимпиада, 1969, 7 класс]. Даны два целых положительных числа m и n .

Известно, что сумма всех делителей m оказалась равна сумме всех делителей n, и сумма чисел, обратных делителям n, оказалась равна сумме чисел, обратных делителям m .

Докажите, что m=n .

Решение. Если k – делитель n, то n/k – тоже делитель n. Если d1, d2,..., ds – все делители числа n, а e1, e2,..., et – все делители числа m, то имеем d1+d2+...+ds=n(1/d1+1/d2+...+1/ds) и e1+e2+.. .

+et = m(1/e1+ 1/e2+...+1/et). Приравнивая левые части и учитывая, что 1/d1+1/d2+...+1/ds = 1/e1+ 1/e2+...+1/et (по условию), получаем m=n .

http://www.ashap.info/Knigi/Matkruzhki/16-AzyTCh .pdf






Похожие работы:

«Иллюстрации Е.В. Москаленко Комнина, Анна Алексеевна. К63 Английский самоучитель и разговорник для тех, кому за. (2  в  одном!) / А.А . Комнина.  — Москва : Издательство АСТ, 2016. — 352 с. — (Самоучитель для тех, кому за.). ISBN 978-5-17-093663-2 Данное пособие создано специально для тех, кто с...»

«Студенческий электронный журнал "СтРИЖ". №1(18). Январь 2018 www.strizh-vspu.ru Теория и методика преподавания учебных дисциплин УДК 372.882 В.В. Бужан (buzhan_1993@mail.ru) Волгоградский государственный социально-педагогический университет ОСОБЕННОСТИ ИЗУЧЕНИЯ ПОСТМОДЕРНИСТСКИХ ПРОИЗВЕДЕНИЙ (...»

«Министерство образования и науки Российской Федерации ФГАОУ ВПО "Российский государственный профессионально-педагогический университет" В. П. Строшков, Ю. И . Категоренко ЭЛЕКТРОХИМИЧЕСКОЕ ФОРМООБРАЗОВАНИЕ ИНСТРУМЕНТА, ЛИТЕЙНОЙ ОСНАСТКИ, ДЕТАЛЕЙ МАШИН Учебное пособие Допущено Учебно-методическим объединением по профессионально-пе...»

«Корнеева Светлана Анатольевна Корнеева С в е т л а н а А н а то л ь е вн а, Белгородский государственны й у н и в е р с и т е т, с т а р ш и й п реподаватель кафедры психология педагогического ф а к у л ь т е т а Глава 7. Разноуровневая природа индивидуальных различий в процессах саморегуля...»

«Управление образования Администрации г. Вологды муниципальное дошкольное образовательное учреждение "Детский сад общеразвивающего вида № 22 "Ласточка" Дополнительная общеобразовательная общеразвивающая программа художественной направленности "Топ-...»

«Айк Харазян Санкт-Петербург "БХВ-Петербург" УДК 004.438 Swift ББК 32.973.26-018.1 Х20 Харазян А. А. Х20 Язык Swift. Самоучитель. — СПб.: БХВ-Петербург, 2016. — 176 с.: ил. — (Самоучитель) ISBN 978-5-9775-3572-4 Книга предназначена для самостоятельного изучения Swift — нового яз...»

«Аттестация учителей начальных классов Демоверсия Квалификационный экзамен для учителей начальных классов Департамент образования администрации Владимирской области ГБУ ВО Региональный информационноан...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

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