Главная страница

Делимость целых чисел Основные понятия и факты


Скачать 359.15 Kb.
НазваниеДелимость целых чисел Основные понятия и факты
Анкор6.pdf
Дата05.04.2017
Размер359.15 Kb.
Формат файлаpdf
Имя файла6.pdf
оригинальный pdf просмотр
ТипДокументы
#14583
Каталогnick1po

С этим файлом связано 28 файл(ов). Среди них: Farmakologia_v_risunkakh_Godovan_2tom.pdf, uchebnik_farmakologia.pdf, Farmakologia_s_retsepturoy_uchebnik_dlya_med_kolledzhey_2014.pdf, Uchebnik_po_farmakologii_Chast_2_pdf.pdf, Uchebnik_po_farmakologii_Chast_1_pdf.pdf, Blok_4.pdf, Особенности питания при заболеваниях ссс.docx и ещё 18 файл(а).
Показать все связанные файлы
Введение
Действия с натуральными и целыми числами знакомы вам с младших классов, когда математика сводится по существу к арифметике. Полезно и поучительно подойти к ним, владея аппаратом алгебры. Задачи о делимости и уравнения в целых числах служат излюбленным материалом для математических олимпиад и факультативов. Всё большую популярность такие задачи приобретают на олимпиадах, проводимых МФТИ, МГУ и другими вузами. В последнее время эти задачи появились ив ЕГЭ по математике (задание C6). Рекомендованные пособия помогут вам в их решении и более глубоком изучении темы.
§1. Делимость целых чисел
1.1. Основные понятия и факты
Напомним основные понятия и факты. Множество натуральных чисел обозначается символом. Множество целых чисел обозначается символом Множество рациональных чисел обозначается символом . Множество действительных чисел обозначается символом В дальнейшем, если не будет сказано иного, мы будем рассматривать только множества целых и натуральных чисел. Натуральное число называется делителем целого числа , если для подходящего целого числа верно равенство
. В этом случае говорят, что делится на и обозначают как «
». Число называют кратным числу . Например,
117 9 117 13 · 9 ; 91 7 91 13 · 7 . Число
2 называют простым, если оно делится только на себя и на единицу. Множество простых чисел обозначают символом . Составными числами называют целые числа, имеющие больше двух различных делителей. Например,
17 – простое число, а 153 17 · 9 – составное. Натуральное число называют общим делителем чисел
, , если и
. Наибольшее такое число называют наибольшим общим делителем m и n и обозначают как НОД
,
(иногда просто
,
). Если наибольший общий делитель двух чисел равен единице, эти числа называют взаимно простыми. Например, 2 – общий делитель чисел 12 и 8, 4 – наибольший общий делитель чисел 12 и 8, те. НОД
12,8 4.
Целое число называют общим кратным чисел и , если и
. Наименьшее натуральное число, кратное и называют наименьшим общим кратными и обозначают как НОК(m,n). Например, 120 – общее кратное чисел 12 и 8, 24 – наименьшее общее кратное чисел 12 и 8, те. НОК
12,8 24. Напомним основные свойства делимости. Свойство 1
. Если целое число делится на число , а число делится на число , то число делится на число . Свойство Если – общий делитель целых чисел и , то
1.
, делятся на ;
2. делится на (точнее – на ). Следствие свойства
2. Если одно из чисел или делится на
, а второе не делится на , тоне делятся на . Действительно, если делится на и, например, делится на
(от противного, то также бы делилось на согласно свойству Свойство 3
. Если целое число делится на взаимно простые делители и , то делится на Свойство 4. Если
(a, b – целые) делится на простое число , то или делится на число . Свойство 5. Если делится на число и взаимно просто с числом, то делится на число .
1.2. Разложение на простые множители.
Основная теорема арифметики Сформулируем основную теорему арифметики Любое натуральные число n, большее единицы, можно разложить в произведение простых чисел. Это разложение единственно, с точностью до порядка следования сомножителей.
Приведём набросок доказательства первой части этой теоремы. Заметим, что если число
1 непростое, оно должно иметь более двух различных делителей. С учётом того, что и
1, должен существовать ещё хотя бы один делитель числа – число ,
1
. Таким образом, или само является простым числом (и разложение получено, или оно раскладывается в произведение
,
1
,
1
. Каждое из чисел a и b также или является простым, или раскладывается далее в произведение ещё более меньших чисел, неравных единице. Данный процесс разложения не может продолжаться бесконечно, ив итоге число n будет представлено в виде произведения простых чисел.
Строгое доказательство того, что такое разложение единственно с точностью до порядка следования сомножителей, первым дал немецкий математик К.Ф. Гаусс (1777 – 1855), внесший крупный вклад в развитие многих областей математики. Пример 1. Найти все простые числа, не превосходящие 100. Решение. Для нахождения таких чисел удобно воспользоваться методом, известным как решето Эратосфена». Этот метод назван в честь греческого математика Эратосфена, жившего в III в. дон. э, и заключается в следующем. Выпишем все числа от 1 до 100 в таблицу
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
Далее, число 1 вычеркнем (оно непростое, числа 2 и 3 оставим как простые и вычеркнем все числа, кратные 2 и 3.
2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97
Далее, оставим число 5 как простое и вычеркнем все числа, кратные
5. Затем тоже самое сделаем с числом 7.
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Все оставшиеся числа будут простые. Это связано со следующим свойством Если число
, то хотя бы один из сомжножителей не превосходит √ Действительно, если предположить противное, те. предположить, что
√ и
√ , то


и возникает противоречие. В примере мы проверили все простые делители, не превосходящие
√100 10. Таким образом, любое составное число, меньшее 100, делится на 2, 3, 5 или 7. Во времена Эратосфена писали на восковых дощечках, а вместо того, чтобы числа вычёркивать, дощечку прокалывали, так что в итоге
она становилась похожей на решето. Отсюда и произошло название метода. Ответ простые числа, меньшие 100, представлены в третьей табли- це.
Итак, для нахождения делителей числа можно воспользоваться следующим способом. Проверим в порядке возрастания делимость числа на простые числа, не превосходящие √ . Если ни на какое из таких чисел не делится, то – простое. Иначе, запишем и будем далее искать делители числа потому же правилу.
Пример 2. Разложите на простые множители число 76557. Решение. Начнём проверять делимость числа 76557 на простые числа, расположенные в порядке возрастания. На 2 число 76557 не делится, зато делится на 3: 76557 = 3×25519. Теперь, будем искать делители числа 25519. Это число не делится на 2, 3, 5, 7, 11, зато делится на
13: 25519=1963×13. Число 1963 также делится нате. Посмотрим на число 151. Заметим, что 151<169=13 2
, значит, если число 151 раскладывается на множители, один из этих множителей будет меньше 13. Но все простые числа, меньшие 13, уже были проверены. Значит, число 151 простое и 76557=3×13 2
×151. Ответ 76557=3×13 2
×151. Пример 3. Докажите, что число
2 11 6 является составным при всех целых . Решение. Разложим этот многочлен на множители, решив для этого уравнение
2 11 6
0. Его корни 6 и
. Отсюда
2 11 6
6 2 1 и, следовательно, 2 11 6
6 2 1 . Таким образом, мы получили разложение целого числа
2 11 6 на два целых числа
6 и 2 1 . Если ни одно из этих чисел по модулю неравно единице, то исходное число является составным. Равенства
6 1;
6 1; 2 1
1 невозможны, равенство
2 1
1 возможно при
0, но при
0 число является составным. Пример 4. Разложите на два сомножителя число
2 2
1. Решение Заметим, что если слагаемое
2 в исходном числе домножить на 2, получится формула суммы квадратов
2 2 2 1

7 2
1 . Тогда добавим и вычтем число 2 в исходную формулу, получив
2 2
1 2
2 2
1 2 . Последнее выражение можно разложить как разность квадратов
2 1
2 2
1 2
2 1
2 . Ответ
2 2
1= 2 2
1 2 2
1 .
1.3. Каноническое разложение числа.
Нахождение количества делителей
Вернёмся к основной теореме арифметики (см. п. 1.2.) Если в разложении натурального числа , большего единицы, встречаются одинаковые простые числа, их удобно группировать в степени. В результате получается

, где
, , … ,
– различные простые числа. Если потребовать, чтобы
, то такое разложение будет абсолютно однозначным. Это разложение называется каноническим. Например,
31752 2 · 3 · 7 Зная каноническое разложение, можно найти все делители числа . Они имеют вид

, где каждый показатель степени может принимать значение от 0 до . Пример 5. Найти все делители числа 28. Решение. Разложим число 28 в канонический вид
28 2
7. Таким образом, в разложении каждого из делителей числа 28 может присутствовать только двойка в степени не более двух, а также семёрка в степени не более единицы. Выпишем все делители в таблицу
2 7
1 2
7 2
2 7
4 2
7 7
2 7
14 2
7 28 Ответ делители числа 28 суть 1, 2, 4, 7, 14 , 28. Заметим, что если сложить все делители числа 28, кроме него самого, мы получим
1 2
4 7
14 28, те. исходное число. Числа, равные сумме своих меньших самого числа делителей, называются совершенными. Таким образом, 28 – совершенное число. Зная каноническое разложение, можно найти количество всех делителей числа. Действительно, пусть

. Делители такого числа имеют вид

, где каждый показатель степени можно выбрать независимо
1 способом (от 0 до
. Все эти числа надо перемножить. Таким образом, количество делителей числа равняется
1 1

1 . Следствие число имеет нечётное количество делителей, только если это число является квадратом. Действительно, нечётное количество делителей равносильно тому, что каждый сомножитель в формуле для нечётен, значит, все числа нечётны, и вхождение каждого простого числа в чётно. Это означает, что является полным квадратом Пример 6. Найти общий вид чисел, имеющих 77 делителей. Решение. Для начала разложим само число 77 на простые множители. Таким образом,
1 1

1 может раскладываться на 2 делителя, 7 и 11, или не раскладываться вовсе. В первом случае получается число вида
, во втором Ответ
, где
, – различные простые числа
, – простое. Нахождение НОД и НОК Запишем каноническое разложение чисел и :

,

. Вообще-то говоря, входящие в состав разложения и простые числа могут быть разными, например
15 3
5 ,
10 2
5 . В таком случае дополним разложение каждого числа недостающими простыми числами в нулевой степени. В этом же примере,
15 2
3 5 , 10 2
3 5 . Итак,

,

, где и
,
0 для всех от 1 до . В таком случае можно записать явные формулы НОД(
, и НОК( ,
:
1. НОД(
, =

, где – меньший из показателей
, .
2. НОК(
,
=

, где – больший из показателей
, .
Также стоит отметить следующее свойство НОК и НОД:
3. НОД(
, × НОК( , Это свойство следует из того, что сумма меньшего и большего из двух показателей равна сумме обоих этих показателей, взятых в произвольном порядке. Пример 7. Найдите НОД (30, 25).
Решение. Запишем канонические разложения чисел 30 и 25 и дополним их недостающими простыми числами.
30 2 · 3 · 5 ; 25 2 · 3 · 5 . По формуле 1 (выше) получим НОД
30,25 2 · 3 · 5 5. Ответ 5.
§2 Десятичная запись числа Всякое натуральное число единственным образом представимо в десятичной записи, которая имеет вид
· 10
· 10
· 10
· где – натуральное число или 0, а
,
,
,
, ,
– цифры от 0 до 9
,
0. Для краткости это число также записывают в виде Крышка сверху ставится, чтобы отличить десятичную запись числа от произведения цифр
·
· Число называется значным в томи только в том случае, если верно неравенство
10 10 Пример 8. Незнайка перемножил все цифры какого-то натурального числа, и получил 2012. Докажите, что Незнайка ошибся. Решение Разложим 2012 на простые множители.
2012 2 · 503. Число 503 является простыми, согласно свойству 4 делимости, если произведение цифр делится на 503, какое-то число должно также делиться на 503. Однако, цифры
1, … ,9 нацело на 503 не делятся, а если среди цифр этого натурального присутствует 0, то и произведение всех цифр также равно 0. Противоречие. Пример 9. В трёхзначном числе первую цифру переставили на последнее место. Могло ли при этом число увеличиться ровно в 8 раз?
Решение. Рассмотрим натуральное трёхзначное число, перепишем его в виде
100
. При перестановке первой цифры на последнее место мы получим число
10
. Составим требуемое уравнение
100 8 10
, откуда получим,
92 79 . Здесь – первая ненулевая цифра исходного трёхзначного числа, а
– число, состоящее из двух, возможно, нулевых, цифр (например,
02 2). Из уравнения,
92 должно делиться на 79. Число 79 – простое, и 92 не делится на 79, поэтому, согласно свойству 4 делимости, делится на
79, однако это невозможно.
Ответ Число увеличиться ровно враз не могло. Пример 10. Что больше
2
или
3
? Решение Сделаем оценки на количество знаков в обоих числах. Заметим, что
2 2
1024 1000 10 , что означает, что в числе
2
хотя бы 91 знак. Наоборот,
3 9
10 , что означает, что в числе
3
не более 90 знаков. Отсюда,
2 Ответ
2 3
§3. Деление целых чисел с остатком
3.1. Основные понятия и факты Теорема о делении с остатком. Всякое целое число можно разделить с остатком на любое натуральное число , те. однозначным образом представить в виде
, 0
, где – (целое число) частное, а – остаток отделения на . Алгоритм деления с остатком заключается в следующем. Если
0
, то следует принять
0,
, а если
, то из большего числа следует вычитать меньшее , пока не получится число, меньшее, чем – остаток. В случае, если m – отрицательное, к нему надо, наоборот, прибавлять число , пока не получится неотрицальное число, меньшее – остаток. Например, найдём остаток при делении числа 31 на число 7. Если вычесть четыре раза число 7 из числа 31, получим число
3 7, таким образом, 31 =
4 · 7 3, остаток равен 3. Теперь найдём остаток отделения числа
31 на число 7. Заметим, что домножив на
(
1 предыдущее равенство, получим
31 4 · 7 3, но из этого не следует, что
3) – остаток. Остаток должен быть неотрицательным. Таким образом, четырёх прибавлений числа 7 к числу
31 недостаточно, нужно прибавить число 7 пятый рази получить
31 5 · 7 4, те. остаток равен 4. Из теоремы о делении с остатком вытекает, что среди любых подряд выписанных n чисел ровно однократно, остальные числа дают все остатки подряд от
1 до
1 (начиная, возможно, нес Воспользовавшись этим, сформулируем следующие утверждения
1. Произведение любых двух последовательных целых чисел делится на 2.
2. Произведение любых трёх последовательных целых чисел делится на 6.

11 3. Произведение любых четырёх последовательных целых чисел делится на 24. Действительно, среди любых двух подряд идущих целых чисел одно чётное, значит, произведение тоже делится на 2. Среди трёх подряд идущих чисел одно делится на 3. Также среди первых двух из трёх подряд идущих чисел одно делится на 2. Т. к. 2 и 3 взаимно простые, то произведение всех трёх чисел делится на 6. Свойство 3 доказывается аналогично среди подряд идущих х чисел найдётся число, делящееся на 4, атак же ещё одно число, дающее остаток 2 при делении на 4, которое также будет чётным. Таким образом, произведение х подряд идущих чисел делится на 4 × 2 = 8. Поскольку это произведение ещё делится на 3, а НОД(3,8) = 1, то произведение всех х подряд идущих чисел делится на 24. Пример 11.
Докажите, что при любом нечётном n число
3 3 делится на 48. Решение. Разложим данный многочлен
3 3
3 1
3 1
1 . Заметим, что – нечётное, поэтому его можно представить в виде
2 1. Тогда
3 1
1 2
2 2 2 2
8 1
1 . Произведение х подряд идущих чисел делится на 6, поэтому всё произведение делится на 48. Пример 12. Найдите все простые числа , при которых числа
2 1 и
4 1 также являются простыми. Решение. Идея решения заключается в том, что хотя бы одно из чисел должно делиться на 3, а следовательно, равняться трём (эти числа по условию простые. Действительно, если делится на 3, а – простое число, то
3, числа
7 2 · 3 1 и 13 4 · 3 1 также простые. Если
1 делится на 3, то 4 1 также делится на 3, и число
4 1
4 1
3 также делится на 3. Это число по условию должно быть простыми потому может быть равным только трём, но
4 1
3. Если
2 делится на 3, то 2 2 также делится на 3, и простое число
2 1
2 2
3 также делится на 3. Но это число простое, и если
2 1
3, тоне является простым числом, противоречие.
Ответ:
3.
3.2. Признаки делимости Вспомним некоторые из признаков делимости и выведем дальнейшие. Пусть натуральное число имеет десятичную запись

12

10 10 10 10
, Сформулируем несколько признаков делимости некоторые из них известны вам из школьного курса),поделив их на 3 группы. Признаки делимости по нескольким последним цифрам Если то а делится на …

делится на 2 или на 5 2 или 5 соответственно
делится на 4 или на 25 4 или 25 соответственно
делится на
8 8
равно 0 10

равно 0 Доказательство всех этих признаков содержат одну и туже идею, продемонстрируем её на примере признака делимости на 4. Заметим, что


00 Но число 100 делится на 4, поэтому
100

также делится на 4, поэтому делимость исходного числа на 4 зависит только оттого, делится ли на 4 или нет. Замечание Все признаки сформулированные, выше, являются также и признаками равноостаточности: остаток отделения на соответствующий делитель исходного числа и выражения, записанного в левой части таблицы совпадает. Этому свойству будут удовлетворять и все признаки, которые будут записаны ниже. Признаки делимости по сумме цифр. Если то а делится на сумма цифр делится на 3 или 9 3 или 9 соответственно знакочередующаяся сумма делится на Докажем признак делимости на 9.

10 10 10 10 99 … 9 99 … 9 99 9

13 9
11 … 1 11 … 1 11 Делимость последнего выражения на 9 совпадает с делимостью суммы цифр исходного числа на 9. Теперь, докажем признак делимости на 11. Заметим, что числа 11, 1001, 100001 (и вообще, все нечётные степени десятки, увеличенные на 1), делятся на число 11. Это легко проверить. Действительно,
1001 990 11, 100001 99990 11 и т. д, откуда делимость на 11 становится очевидной. Более строго это следует из формулы сокращённого умножения, которая в нашем случае может быть записана в виде
10 1
10 1 10 10 10 10 1 . Числа, состоящие из чётного числа девяток (99, 9999 – чётные степени десятки, уменьшенные на 1), делятся на число 99 и, следовательно, на число 11. Тогда наше число может быть переписано в виде
11 1
99 1
1001 1
11 99 Все подчёркнутые числа кратны 11, следовательно, остаток отделения на число 11 равен остатку знакочередующейся суммы цифр. В последней группе признаков делимости рассматриваются суммы двузначных или трёхзначных граней – двузначных или трёхзначных чисел из цифр данного числа, справа налево. Так, в числе 12345 есть три двузначные грани 1 | 23 | 45.
3. Признаки делимости по сумме граней. Если то а делится на сумма двузначных граней делится на
11 11 сумма трёхзначных граней делится на 3737 знакочередующаяся сумма трёхзначных граней делится на 7, 11, 13 7, 11 13 соответственно Докажем, например, второй признак делимости на 11.

100 10000 99 9999
Т. к. 99 делится на 11, то число в правой скобке делится на 11, следовательно, делимость исходного числа на 11 зависит от суммы двузначных граней, написанной впервой скобке. Хотя доказательство оставшихся двух признаков является аналогичным доказанному признаку и мы приводить его не будем, отметим разложение числа 1001 на простые множители, которое позволило сформулировать признаки делимости на 7, 11 и 13:
1001 7 11 Пример 13.
Делится ли на 7 число 1234567890? Решение. Воспользуемся признаком делимости на 7 и посчитаем знакочередующуюся сумму трёхзначных граней 890 – 567 + 234 –
– 1 = 556. Число 556 на 7 не делится, значит, исходное число на 7 также не делится. Ответ не делится Пример 14. При каких натуральных число
4 1 делится на 5. Решение. Посмотрим на последнюю цифру числа
4 .
1 2 3 4 5 4
4 16 64 256 1024 Несложно заметить, что прич тных степенях она будет равняться шести, при нечётных – четырём. Эта закономерность будет продолжаться и дальше умножая на 4 число, оканчивающееся на 6, мы получим число с последней цифрой 4 и, наоборот, умножая на 4 число с последней цифрой 4, мы получим число, оканчивающееся на 6. Если прибавить единицу, мы получим, что последняя цифра полученного числа равняется 5 при нечётных степенях, и равняется 7 прич тных. По признаку делимости на 5 последняя цифра числа, делящегося на 5, должна быть либо 0, либо 5, поэтому
4 1 делится на 5 только при нечётных Ответ
4 1 делится на 5 при нечётных и не делится – прич т- ных.
3.3. Вычисление НОД с помощью алгоритма Евклида Чтобы вычислить НОД двух чисел, необязательно знать разложение этих чисел на простые множители. Существует иной способ, основанный наделении с остатком. Он известен как алгоритм Евклида.
Сформулируем свойство НОД двух чисел, которое используется в алгоритме Евклида. Пусть
, тогда
НОД(a, b) = НОД(a – b, b). Это легко доказывается при помощи свойства 2 делимости целых чисел. Докажем, что общие делители чисел
, и чисел
, совпадают. Действительно, пусть
, делятся на , тогда
, также делится на . Обратно, пусть
, делятся на . Тогда также на него делится. Если всеобщие делители совпадают, то наибольший из них (НОД) также должен совпадать. Теперь перейдём к формулировке алгоритма Евклида. Пусть Разделим с остатком число на число :
, 0
. Тогда
НОД(a, b) = НОД(r, b) = НОД(b, r). Это свойство получается многократным применением свойства
НОД(a, b) = НОД(a – b, b). Теперь заменим число на число , – на число и проделаем тоже самое с числами и и т. д. Эти операции закончатся, когда одно число поделится на другое нацело, делитель и будет являться НОД чисел и . Пример 15.
С помощью алгоритма Евклида найдите НОД чисел
1848 и 627. Решение. Начнём операцию деления с остатком
1848 627 2 594, поэтому НОД(1848,627) = НОД(627,594),
627 594 1 33, поэтому НОД(627,594) =НОД(594,33),
594 33 18, те. число 594 разделилось на 33 нацело. Это означает, что за 3 шага алгоритм Евклида выдал ответ 33. Ответ НОД
1848,627 33. Пример 16. Докажите, что при целых значениях числа 2 4 и
2 1 не могут одновременно делиться ни на какие простые числа, отличные от 3.
Решение. Для доказательства применим алгоритм Евклида. Най- дм, какие значения может принимать НОД
2 4, 2 1 . Для этого, воспользовавшись несколько раз свойством вначале параграфа, получим НОД
2 4, 2 1
НОД
4, 2 1 . Это следует из того, что
2 4
4 2
1 .
4, 2 1 Вычтя из
2 1 дважды число
4, получим НОД 2 1,
4 НОД 9
, x 4
Число 9 не зависит от
,
это значит, что НОД
9
,
4 который равняется НОД исходных выражений, делит число 9. Таким образом, НОД
2 4, 2 1 может принимать значения 1, 3,
9, из чего и следует утверждение задачи. Алгоритму Евклида уже более 2 тыс. лет. Он сформулирован в Началах Евклида, где из него выводятся свойства простых чисел, наименьшего общего кратного и т. д. Алгоритм имеет много практических применений. Ещё древние пифагорейцы знали его как способ нахождения наибольшей общей меры двух соизмеримых отрезков. К середине
XIV в. алгоритм Евклида был распространён на многочлены от одного переменного, а в дальнейшем этот алгоритм был определён и для ряда других алгебраических объектов.
§4. Решение уравнений в целых числах
4.1. Линейное диофантово уравнение с двумя неизвестными В этом разделе рассматривается линейное уравнение
, где
, , – целые числа, причем
0 (иначе это уравнение сне более одной неизвестной. Уравнения с целыми числами с двумя (и более) неизвестными наряду с большим количеством других интересных задач рассматривал в своей книге Арифметика греческий математик Диофант Александрийский в. Такие уравнения были впоследствии названы его именем. Пример 17.
Докажите, что монетами в 2 и 5 рублей можно заплатить любую натуральную сумму рублей, кроме 1 и 3. Решение. Пусть сумма, которую нужно составить, равняется рублей, и мы заплатим её монетами по 2 рубля и монетами по 5 рублей. Отсюда получим уравнение
2 5
. Выразим через :
5 Наша задача – найти хотя бы одно решение этого уравнения в целых неотрицательных числах. Если делится на 2, тов качестве такого решения можно взять
0,
/2. Если жене делится на 2, то можно взять Здесь не будет являться отрицательным, если
5. Таким образом, любую натуральную сумму рублей, кроме 1 и 3, можно заплатить монетами в 2 и 5 рублей. Замечание Если же в этой задаче разрешить давать сдачу (также только монетами 2 и 5 рублей, то тогда можно будет с учётом сдачи заплатить любую сумму рублей.
Перейдём к решению уравнения Теорема. Уравнение имеет бесконечное множество целочисленных решений, если делится на НОД
, и не имеет целочисленных решений в противном случае. Условие «
делится на НОД , », частности, всегда выполнено, когда числа и взаимно просты.

17
Диофантово уравнение можно решать последующему алгоритму
1. Разделим обе части уравнения на НОД
, . Числа и
, поделённые на свой НОД, станут взаимно простыми. Если число , разделённое нацело на НОД
, , не является целым, то уравнение решений не имеет (слева стоит целое число, справа – нецелое. Таким образом, мы пришли к равносильному уравнению
, где НОД
,
1.
2. Итак, пусть теперь есть уравнение
, где числа и являются взаимно простыми. Найдём какое-то одно (так называемое частное) решение этого уравнения – (
,
. Это можно сделать пут м подбора или с помощью алгоритма Евклида (см. конец этого раздела. Выпишем ответы
, Почему все ответы имеют такой вид Пусть (x
0
, y
0
) – решение уравнения
. Рассмотрим выражение. Оно равняется нулю
0. Таким образом, числа и являются решениями уравнения. Перепишем это уравнение в виде
. Так как числа и – взаимно просты, число должно делиться на число , те. при каком-то целом
. Подставим в уравнение
, получим
, что в свою очередь после сокращения на преобразуется к виду
. Итак,
0 0
,
,
x x
bt
y y
at

= −

⎨ − откуда и получаем выписанные в п. 3 ответы. Пример 18. Решите уравнение 4
100. Решение. Разделим обе части уравнения на НОД(10,4) = 2, получив уравнение
5 2
50. Подбором получаем частное решение
0 0
10,
0.
x
y
=
= Затем выпишем все решения этого уравнения
10 2
5 Ответ
10 2
5 Опишем процесс нахождения частного решения с помощью алгоритма Евклида на примере диофантова уравнения
7 18 2.
Пример 19. Найдите частное решение уравнения
7 18 Решение. Для начала найдём частное решение уравнения
7 18 1, затем, домножив полученное решение на 2, получим частное решение уравнения
7 18 2.
Найдём НОД(18,7) с помощью алгоритма Евклида. 18 = 7 × 2 + 4, поэтому НОД(18,7) = НОД(7,4). Будем записывать каждое новое число, к которому мы приходим, выполняя алгоритм Евклида, в виде
7 18 . Так, 4 = 18 – 7 × 2. Затем НОД(7,4) = НОД(4,3), где 3 = 7 – 4 = 7– (18 –7×2) = 7×3 – 18. Наконец, НОД(4,3) = НОД(3,1) = 1, причём 1 = 4 – 3 = (18 – 7×2) –
– (7×3 –18) = 18×2 – 7×5. Вот мы и получили частное решение уравнения
7 18 1:
5,
2. Отсюда частное решение уравнения
7 18 2 имеет вид
0 0
10,
4.
x
y
= −
= Решая задачу другими способами, можно найти и другие частные решения. Например,
0 0
8,
3.
x
y
=
= − Ответ
10,
4.
*
4.2. Примеры решения нелинейных уравнений Пример 20. (ЕГЭ, тренировочный вариант Группу школьников нужно перевезти из летнего лагеря одним из двух способов либо двумя автобусами типа Аза несколько рейсов, либо тремя автобусами типа В за несколько рейсов, причём в этом случае число рейсов каждого автобуса типа В будет на один меньше, чем рейсов каждого автобуса типа А. В каждом из случаев автобусы заполняются полностью. Какое максимальное количество школьников можно перевезти при указанных условиях, если в автобус типа В входит на 7 человек меньше, чем в автобус типа А Решение. Пусть в автобус типа В входит человек (тогда в автобус типа А входит
7 человек, и автобусы типа B должны совершить рейсов (тогда автобусы типа A должны совершить
1 рейс. По условию задачи составим выражение для количества детей, перевезённых обоими способами
2 7
1 3 . Выразим переменную этого выражения через .

19 14 14 14 2
14 Выделим целую часть числа
14 14
;
2
y
y
+

14 14 42 14 Напомним, число должно быть целым, отсюда получаем, что число должно быть делителем числа 42.
Переберём все делители числа 42 и выясним, какое максимальное количество детей (
3
можно увезти
2 1 2 3 6 7 14 21 42 3 4 5 8 9 16 23 44 56 35 28 21 20 17 16 15 3
504 420 420 504 540 816 1104 1980 Максимальное количество школьников, которое можно перевезти согласно условиям задачи, равно 1980. Ответ 1980. Пример 21. Решите в целых числах уравнение Решение. Перепишем уравнение в виде
5 5
0;
5 5
5 25 0;
5 5
25. Заметим, что 25 можно разложить на множители (в том числе отрицательные) только следующими способами
25 1 25 5 5 1
25 5
5 . Из каждого из разложений получаем решения. Ответ ,
6,30 ; 30,6 ; 10,10 ; 4, 20 ;
20,4 ; 0,0 . Пример 22. Решите в целых числах уравнение
2 Решение. Перепишем это уравнение в виде
2 7. Это разложение можно получить следующим образом запишем выражение и вынесем за скобки
2 2
2
x
x
y
.
y
y


⎛ ⎞
− −


⎜ ⎟


⎝ Далее, решив квадратное уравнение
2 2 0
x
x
y
y
⎛ ⎞
− − =
⎜ ⎟
⎝ ⎠
(корни
1
x
,
y
= −

20 разложим его на множители 2
x
x
.
y
y

⎞⎛

+


⎟⎜


⎠⎝

Отсюда, после домножения на , получается написанное выше разложение
(
)(
)
2
x y x
y Т. к. и
2 – целые числа, то нужно посмотреть на разложение числа 7 на два целых множителя. Возможные разложения выпишем в таблицу
7 1
7 1
2 1
7 1
7
Получаются 4 системы линейных уравнений. Решим одну из них первую
7,
2 Получим
5,
2. Остальные системы выписываются аналогично, и все полученные решения будут являться целыми. Ответ ;
5, 2 ; 3, 2 ;
3,2 . В обоих примерах мы раскладывали многочлен на множители и использовали свойства делимости. Пример 23. Решите в целых числах уравнение
7 2
23 0. Решение. В это уравнение переменная входит впервой степени, выразим её через :
2 7
23 0,
3 7
23 Сделаем замену
2
t x
.
= − Тогда
2;
x t
= +
3 3
3 6
12 8
x
t
t
t
= +
+
+
и, следовательно+ +По условию и – целые, поэтому 17 должно делиться на
. Возможны варианты
1 1
17 17 3
1 19 15 29 17 397 Ответ ; 1,17 ; 19,397 ;
15,191 . Пример 24. Найдите все целые
, при которых 2 1
, где – натуральное число.
Решение. Будем считать неотрицательным (затем добавим число "– " в ответ)
Перепишем это уравнение в виде
2 1
1 1 . Заметим, что неотрицательные делители числа
2 также обязаны являться степенями двойки, поэтому
1 2 ,
1 2 . Числа
1 и
1 – делители числа 2 – неравны единице, поэтому оба этих числа являются натуральными степенями двойки.
С другой стороны, среди двух последовательных чётных чисел одно делится на 4, а второе на 4 не делится. Поскольку второе число на 4 не делится и при этом оно не должно содержать отличных от 2 простых делителей, то это число равно 2. Таким образом, нужно рассмотреть 2 случая а.
1 2,
1 – не подходит. б.
1 2,
3 – подходит (
3 . Ответ. Пример 25. Решите в натуральных числах уравнение
1 2 . Решение. Разложив левую часть, получим
1 1
2 . Т. к. числа и
– натуральные,
1 2; 1 2, значит, оба числа –
1
и
1
– являются натуральными степенями двойки. Пусть
1 2 . Выразив из этого уравнения , получим, 1 2
2 · 2 2. Это число также должно являться степенью двойки. Если
1, то ,
1,2 – решения нашего уравнения. Если
2, то 1 10, что не является степенью двойки решений в данном случае нет. Если
3, то 2 · 2 2
0 и 2 2 · 2 2
2 . Докажем, что
2 2 · 2 2
2
. Это неравенство можно переписать в виде
2 2
2 2 · 2 2; 2 2
1. Последнее неравенство является верным, т. к. при
3 верно
2 2
3, что приведёт к неравенству 2 2
0 1. Таким образом, мы получили, что число
1 2
2 · 2 2 заключено строго между двумя соседними степенями двойки,
2 2
2 · 2 2
2 , а, значит, само степенью двойки не является. Противоречие, решений при
3 нет. Ответ ,
1,2 .
*
§5. Сравнения Пусть задано натуральное число
, которое мы в дальнейшем будем называть молулем.
Будем говорить, что числа
и сравнимы по модулю , если
делится на
. Это утверждение обозначают как mod Если число не делится на , то говорят, что несравнимо с по модулю
, и обозначают как mod По теореме о делении с остатком числа и можно представить в виде
, 0
;
, 0
, где и – остатки, возникающие при делении чисел и на число Заметим, что
;
, откуда
. Отсюда, если делится на , то также делится на . Т. кто. Поэтому делится на только водном случае
0,
. Очевидно, верно и обратное если
, то делится на Поэтому числа и сравнимы по модулю тогда и только тогда, когда они дают одинаковые остатки при делении на . Рассмотрим множество чисел, которые дают остаток при делении на (это множество является подмножеством целых чисел. Из утверждения выше следует, что любые два числа изданного множества будут сравнимы между собой по модулю . Всего разных остатков при делении на имеется штук (от 0 до
1). Таким образом, множество целых чисел можно разбить на множеств, не содержащих общих элементов, каждое из которых характеризуется остатком отделения чисел множества на Например, прибудет три множества множество чисел, делящихся на 3 (имеет вид
3 ,
); множество чисел, дающих остаток 1 при делении на 3 (
3 1,
, и множество чисел, дающих остаток 2 при делении на 3 (
3 Такие множества называются классами вычетов. Таким образом, множество целых чисел разделено на классов вычетов по модулю . Из всего вышесказанного следует, что числа и сравнимы по модулю тогда и только тогда, когда они принадлежат одному классу вычетов при делении на . Основные свойства сравнений. Свойство 1. Сложение и вычитание сравнений) Если

mod и mod то mod . Следствие 1.1. К обеим частям сравнения можно прибавить одно и тоже число если mod , то +
mod . Свойство 2.
(Умножение сравнений. Если

mod и mod то mod .
Следствие 2.1. Обе части сравнения можно умножать на одно и тоже число если mod , то mod . Следствие 2.2. Обе части сравнения можно возводить в одну и туже степень если mod , то mod . Пример 26. Доказать, что при любом натуральном число
6 19 2
делится на Решение. Докажем, что
6 19 2
0 mod 17 . Согласно свойству 1 сравнений, каждое число в сумме можно заменить на число, дающее такой же остаток при делении на 17. Заметим,
6 36 . Т. кто, согласно следствию 2.2, 36 2 mod 17 . Аналогично,
19 2 mod 17 . Заменим числа 6 и 19 на сравнимые им. Тогда потребуется доказать, что
2 2
2 0 mod 17 , но это очевидно, т. кв левой части сравнения при вычислении получается число 0. Таким образом,
6 19 2
0 mod 17 , те делится на
17.
Приведём другой способ решения примера, который не использует свойства сравнений, но использует метод математической индукции, согласно которому, если доказываемое утверждение верно при начальном
, (обычно
1 (основание индукции) и из предположения, что доказываемое утверждение верно при

(предположение индукции, следует его справедливость для

1 (шаг индукции, то утверждение верно при всех
. Стоит отметить, что обе части (основание и шаг индукции) одинаково важны при доказательстве утверждений.
Вернёмся к примеру и проверим основание индукции при
1. Действительно
6 19 2
51 17. Пусть при выражение
6 19 2
делится на 17 предположение индукции. При
1 получим
6 19 2
36 · 6 19 · 19 2 · 2 36 · 6 19 2
17 · 19 34 · 2 36 17 · 19 34 · Т. к. по предположению индукции
17, то
36 17 · 19 34 · 2
также делится на 17. Таким образом, шаг индукции доказан и, согласно методу математической индукции, исходное утвержение верно при всех
1. Пример 27.
Решите в целых числах уравнение
2011. Решение. В данной задаче требуется применить сравнения по модулю. Остаток отделения числа на 4 зависит от остатка отделения числа на тот же модуль. Выпишем всевозможные остатки приделе- нии числа в таблицу, туда же запишем остатки от числа . остаток от
0 1
2 остаток от
0 1
0 Проверим, например, остаток 3. Действительно,
3 9
1 mod 4 . Таким образом, по модулю 4 квадраты чисел могут давать только остатки 0 и 1, поэтому сумма двух квадратов может давать остатки 0, 1,
2 и не может давать остатка 3. Но,
2011 3 mod 4 . Поэтому решений в целых числах у исходного уравнения нет. Ответ нет решений. Пример 28.
Существует ли натуральное число такое, что
2012 2014
? Решение. В отличие от предыдущей задачи, если использовать сравнения по модулю 4, противоречия не получится. Действительно, оба числа
2012
и
2014
делятся нате. должен давать остаток при делении на 4, и такое возможно. Однако отсутствие противоречия при рассмотрении модуля 4 не гарантирует существования такого. Модуль, по которому возникает противоречие, обычно ищут методом перебора среди возможных модулей. Так, в этом примере возникает противоречие по другому модулю
3. Заметим, 2012 2
1 mod 3 ; 2014 1 mod 3 . Воспользовавшись следствием 2.2 (возведение сравнения в степень, а затем свойством 1 (сложение сравнений, получим,
2012 2014 1
1 2 mod 3 . Таким образом, квадрат натурального числа должен давать остаток 2 при делении на 3. Однако квадраты натуральных чисел также могут давать только остатки и 1 при делении на 3: (
0 0 mod 3 ; 1 1 mod 3 ; 2 1 mod 3 . Следовательно, такого натурального не существует. Пример 29. Найдите остаток отделения на Решение. Следствие 2.2 свойств сравнений (возведение сравнения в степень) позволяет основание степени
36 · 18 заменить на сравнимое с этим основанием по модулю 17 число. Это число мы найдём, воспользовавшись свойством 2 сравнений (умножение сравнений, заменив числа 36 и 18 на их остатки по модулю 17, те. на числа 2 и 1.
Записывая формулами вышесказанное
36 2 mod 17 ;
18 1 mod 17 , получим 36 · 18 2 · 1 2 mod 17 . Затем последствию. Итак, нужно найти остаток отделения на 17. Будем возводить число 2 последовательно в натуральные степени
(1, 2, 3, 4, …) и посмотрим на остатки отделения получившихся чисел на 17. Всего теоретически возможно 16 разных остатков отделения числа
2 на 17 (все, кроме 0). Таким образом остатки когда-то должны повториться. Выпишем в таблицу несколько первых степеней, найдём их остатки по модулю 17 и определим, когда остатки повторятся.
1 2
3 4 5 6 7 8 9 10 2
2 4 8 16 32 64 128 256 512 1024 остаток 2 4 8 16 15 13 9 1 2 4 Замечание При выписывании таблицы остатков необязательно вычислять все степени двойки, для вычисления остатка следующей степени достаточно знать остаток от предыдущей степени. Например, най- дм остаток от
2 по модулю 17. Мы уже знаем, что 2 15 mod 17 . Тогда
2 2 · 2 и, по свойству 2 сравнений, получим 2 · 2 2 · 15 30 13 mod 17 . Итак, мы выписали первые 10 степеней двойки и нашли повторение
2 2
2 mod 17 . Т. к. из замечания выше следует, что остаток следующей степени зависит только от остатка текущей степени, далее остатки будут повторяться
2 2
4 mod 17 ; 2 2
8 mod 17 ;
2 2
16 mod 17 и т. д Таким образом, эти остатки будут представлять собой периодическую последовательность с периодом
9 1
8.
Найдём теперь остаток от
2 . Для этого найдём остаток от числа 50 по модулю периода последовательности – числа 8. Получим
50 2 mod 8 , поэтому 2 2
4 mod 17 . Ответ 4.

26
Приведём без доказательства теорему, полезную при решении задач на делимость степеней. Она принадлежит Пьеру Ферма, нов отличие от Великой теоремы Ферма, легко доказывается и известна как малая теорема Ферма
Малая теорема Ферма Пусть – простое число, – натуральное число. Если не делится на
, то
делится на . На языке сравнений, если
0 mod , то
1 mod . Малая теорема Ферма была бы полезна при решении предыдущего примера так согласно теореме,
2 1 mod 17 , поэтому 2 2
2 2
· 2 1 · 2 mod 17 4 mod17 , откуда сразу следует ответ 4.
Рекомендуемая литература

1.
Агаханов Н.Х., Подлипский О.К. Математические олимпиады Московской области 1993 – 2005. Изд. 2. – М МФТИ, 2006.
2.
Алтуфова Н.Б., Устинов А.В. Алгебра и теория чисел. Сборник задач для математических школе изд. М МЦНМО, 2002.
3.
Виленкин НА, Шибасов Н.П., Шибасова З.Ф. За страницами учебника математики 10–11. – М Просвещение, 1996.
4.
Галкин В.Я., Сычугов Д.Ю., Хорошилова Е.В. Конкурсные задачи, основанные на теории чисел. – М Макс Пресс, 2003.
5.
Колосов В.А. Теоремы и задачи алгебры, теории чисел и комбинаторики М Гелиос АРВ, Математическая энциклопедия абитуриента, вып.
1: Петрович А.Ю., Сидоров Ю.В., Шабунин МИ. Числа и многочлены М МФТИ и РОУ, 1992.
7.
Нестеренко Ю.В. Простые и составные числа (в сб. Факультативный курс по математике 7–9», сост. Никольская ИЛ. – М Просвещение, 1991.
8.
Фалин Г.И., Фалин АИ Алгебра на вступительных экзаменах по математике в МГУ. – М БИНОМ. Лаборатория знаний, 2006.
9.
Черемушкин А.В. Лекции по арифметическим алгоритмами криптографии. – М МЦНМО, 2002.
10.
Чубарова Е.И., Чубаров И.А. Элементы теории сравнений и их применение к решению задач. – Потенциал, 2005, №8.

27 11.
Пратусевич М.Я., Рукшин СЕ, Столбов КМ, Ященко ИВ. ЕГЭ
2011. Математика. Задача С. Арифметика и алгебра. – М
МЦНМО, Контрольные вопросы Числа

, – целые, , – натуральные Пусть делится на . Верно ли, что или делится на ? Сравните со свойством 4 делимости)
2(2).
Пусть делится на и . Верно ли, что делится на
? сравните со свойством 5 делимости.
3(3).
Сумма и произведение чисел и делится на . Что можно сказать о делимости чисел и на , если оно (а) простое, (б) составное В доказательстве первой части основной теоремы арифметики стр. 4) присутствует фраза Данный процесс разложения не может продолжаться бесконечно. Объясните, почему.
5(2).
Допишите последнюю цифру числа 1234567 так, чтобы полученное число делилось на 3, 9, 4, 8, 25, 11.
6(2).
Существует ли натуральное число, при делении на 21 дающее остаток 6, а при делении на 15 – остаток 10?
7(2).
Найдите НОД(80,46) с помощью алгоритма Евклида.
8(2).
Решите диофантово уравнение
12 9
3. Задачи
1.
Докажите, что при всех целых : а 4 делится наб не делится на 120.
2(4).
При каких целых значениях число
2 является простым Найдите все шестизначные числа вида
2 01 2, делящиеся на
132.
4(4).
Пусть
, , , – попарно различные цифры. Докажите, что число не делится на число
5(4)
Известно, что произведение двух последовательных чётных чисел заканчивается на цифру 4. Какая может быть предпоследняя цифра этого произведения

28
6(4).
Известно, что некоторое 2012-значное число образовано цифрами и делится на 8. Какие остатки при делении на 125 может принимать это число
7(7). а Найдите НОД и НОК чисел 1643 и 1272. б Решите диофантово уравнение
1643 1272 318.
8(6).
Решите в целых числах уравнения а 2
3 4; б 2
4 ; в.
9
*
(5).
Докажите, что при любом натуральном значении число
5 · 7 2 делится на 41.
10
*
(3).
Докажите, что уравнение
4 3
11 не имеет решений в натуральных числах.

перейти в каталог файлов
связь с админом