Исследовательская работа "Делимость и остатки"

Решим задачу: найти остаток от деления числа 22 • 50 + 44 • 10 на 3. Для этого не обязательно вычислять выписанное выражение. Поступим так: заменим каждое из чисел на его остаток от деления на 3. Получим выражение 1 • 2 + 2 • 1. Это число равно 4 и дает остаток 1 при делении на 3. Мы утверждаем, что остаток исходного выражения от деления на 3 также равен 1. Дело в том, что верны следующие утверждения:

1. Сумма любых двух натуральных чисел и сумма их остатков имеют одинаковые остатки при делении на 3.

2. Произведение любых двух натуральных чисел и произведение их остатков имеют одинаковые остатки при делении на 3.

Задача 1. Найдите остатки от деления

а) 1990 • 1991 • 1992 + 1993³ на 7;

б) 9¹⁰⁰ на 8.

Решение:

Произведение (сумма) двух целых чисел даёт такой же остаток при делении на n, как и произведение (сумма) их остатков при делении на n.

а) Данное выражение даёт при делении на 7 такой же остаток, как и 2·3·4 + 5²= 49.(1990:7= 284 ост.2, 1991:7= 284 ост.3, 1992:7= 284 ост.4, 1993:7= 284 ост.5) 49 делится на 7 остаток 0

б) Данное выражение даёт при делении на 8 такой же остаток, как и 1¹⁰⁰= 1.

Ответ: а) 0; б) 1.

Решение следующей задачи содержит очень важную идею.

Задача 2. Докажите, что п³ + 2п делится на 3 для любого натурального п. Решение: Число п может давать при делении на 3 один из трех остатков: 0,1,2. Рассмотрим три случая.

Если п дает остаток 0, то и п ³ и 2п делятся на 3 и поэтому п ³ + 2п также делится на 3.

Если п дает остаток 1, то п ³ дает остаток 1, 2п - остаток 2, а 1 + 2 делится на 3.

Если п дает остаток 2, то п² дает остаток 1, п ³ - остаток 2, 2п - остаток 1, а 2 + 1 делится на 3.

Требуемое доказано.

Задача 3. Докажите, что п⁵ + 4n делится на 5 при любом натуральном п.

Задача 4. Докажите, что п² + 1 не делится на 3 ни при каком натуральном п.

Задача 5. Докажите, что п ³ + 2 не делится на 9 ни при каком натуральном п.

Задача 6. Докажите, что п³ — п делится на 24 при любом нечетном п.

Задача 7. а) Докажите, что р² — 1 делится на 24, если р - простое число и

р3.

б) Докажите, что р² —q² делится на 24, если р и q - простые числа,

большие 3.

Задача 8. Натуральные числа х, у, z таковы, что х² + у² = z². Докажите, что хотя бы одно из этих чисел делится на 3.

Задача 9. Докажите, что сумма квадратов трех натуральных чисел-, уменьшенная на 7, не делится на 8.

Перейдем к следующему циклу задач:

Задача 10. Найдите последнюю цифру числа 1989¹⁹⁸⁹.

Решение: Заметим сначала, что последняя цифра числа 1989¹⁹⁸⁹ совпадает с последней цифрой числа 9¹⁹⁸⁹. Выпишем последние цифры нескольких начальных степеней числа 9: 9, 1, 9, 1, 9, ....

Так как при нахождении последней цифры очередной степени числа 9 достаточно умножить на 9 лишь последнюю цифру предыдущей степени, то ясно, что за 9 следует 1 (9 • 9 = 81), а за 1 - 9 (1 • 9 = 9).

Таким образом, нечетные степени девятки оканчиваются на 9. Поэтому последняя цифра числа 1989¹⁹⁸⁹ - девятка.

Задача 11. Найдите последнюю цифру числа 2⁵⁰.

Решение: Выпишем последние цифры нескольких начальных степеней двойки: 2, 4, 8, 6, 2,Видим, что 2⁵ также, как и 2¹, оканчивается на 2. Поскольку очередная цифра полностью определяется последней цифрой предыдущей степени, то произойдет "зацикливание": 2⁶ (как и 2²) оканчивается на 4, 2⁷ (как и 2³) - на 8, 2⁸ - на 6, 2⁹ - на 2 и т.д. Поскольку длина цикла равна 4, то последняя цифра числа 2⁵⁰ определяется остатком от деления числа 50 на 4. Так как он равен 2, то последняя цифра числа 2⁵⁰ совпадает с последней цифрой числа 2², то есть равна 4.

Задача 12. Найдите остаток от деления 2¹⁰⁰ на 3.

Задача 13. Найдите остаток от деления З¹⁹⁸⁹ на 7.

Задача 14 Докажите, что 2222^555S + 55 55²²²² делится на 7.

Задача 15. р и р² + 2 - простые числа. Докажите, что р³ + 2 - также простое число.

Задача 16. Докажите, что а³ + Ь³ + 4 не является кубом целого числа ни при каких натуральных а и Ь.

Задача 17. Докажите, что число 6п³ + 3 не является шестой степенью целого числа ни при каком натуральном п.

Решение задач смотри в приложении 2

Рассмотрим ещё несколько задач не объединенных какой-либо идеей или методом решения.

Задача 18. а) а + 1 делится на 3. Докажите, что 4 + 7а делится на 3.

Решение

7а + 4 = 7(а + 1) - 3 , т.к. a+1 делится на 3 и 3 делится на 3, то и их разность 7(а + 1) - 3 делится на 3.

б) 2 + а и 35 - b делятся на 11. Докажите, что делится на 11.

Решение

б) a + b= (2 +a) – (35 –b) + 33. Каждое из слагаемых делится на 11, значит и вся сумма a + b делится на 11.

Задача 19. Найдите последнюю цифру числа 1² + 2² + ... + 99².

Решение

1²+ 2²+ ... + 99²≡ 10(1²+ 2²+ ... + 9²) = 0 (mod 10).

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

Решение

Если n чётно, то сумма тоже чётна (и больше 2).

Если же n нечётно, то сумма делится на среднее из наших чисел: сумма первого и последнего (второго и предпоследнего, и т.д.) в два раза больше среднего числа. Значит сумма является составным числом.

Задача 21. Найдите наименьшее число, дающее следующие остатки: 1 - при делении на 2, 2 - при делении на 3, 3 - при делении на 4, 4 - при делении на 5, 5 - при делении на 6.

Заметим, что это число, увеличенное на 1, делится на 2, 3, 4, 5, 6.

НОК(2, 3, 4, 5, 6) – 1 =59.

Ответ: 59

Задача 22. Докажите, что если (п — 1)! + 1 делится на п, то п - простое число.

Решение

Пусть n+ 1 – составное число. Если p – некоторый его простой делитель, то p ≤ n. Значит, n! делится на p, а n! + 1 не делится. Противоречие.

Отдельно рассмотрим следующие две задачи:

Задача 23! Докажите, что существует такое натуральное п, что числа п + 1, п + 2, ..., п + 1989 - составные.

Решение:

Попробуем рассказать, как пойти по самому простому пути: сделаем так, чтобы п + 1 делилось на 2. п + 2 также должно быть составным, но делиться на 2 уже не может. Попытаемся опять пойти по самому простому пути: хотелось бы сделать так, чтобы п + 2 делилось на 3. Продолжая в том же духе, можно пытаться найти число п такое, что п+1 делится на 2, п + 2 - на 3, п + 3 - на 4 и так далее. Это равносильно тому, что п - 1 делится на 2, 3, 4, ..., 1990. Такое число, конечно, существует - например, 1990!. Итак, в качестве искомого п можно взять число 1990! + 1.

Задача 24! Докажите, что существует бесконечно много простых чисел.

Решение: Предположим противное. Пусть р₁, р₂,… р _п - все простые числа. Рассмотрим число р₁р₂…р _п + 1. Это число не делится ни на одно из чисел р₁, р₂,… р _п и, следовательно, не может быть разложено в произведение простых. Противоречие.

.

1. Алгоритм Евклида

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

НОД(1381955; 690713) = 23

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

Алгоритм Евклида основан на следующем простом соображении: любой общий делитель чисел а и b (а b) делит также число а — b; кроме того, любой общий делитель чисел b и а— b делит число а. Тем самым,

НОД(а, b) = НОД(b,а- b).

Покажем, как работает алгоритм Евклида для конкретных чисел. Найдем наибольший общий делитель чисел 451 и 287:

НОД(451,287) = НОД(287,164) = НОД(164,123) = НОД(123,41) =НОД(82,41)= = НОД(41,41) = 41.

Заметим, что алгоритм Евклида можно ускорить: заменять а не на а - b, а сразу на остаток от деления а на b. Продемонстрируем это на примере наших чисел:

НОД(1381955,690713) = НОД(690713,529) =

= НОД(529,368) =

= НОД(368,161) =

= НОД(161,46) =

= НОД(46,23) =

= НОД(23,0) =

= 23.

Как видно, этот метод очень быстро приводит к результату.

Задача 1. Найти наибольший общий делитель чисел 2п + 13 и п + 7.

Решение

НОД(2 п + 13, п + 7) = НОД(п + 7, п + 6) = НОД(п + 6,1) = 1.

Задача 2. Докажите, что дробь - несократима ни при каком натуральном п.

Решение

НОД(30n+ 2, 12n+ 1) = НОД(12n+ 1, 18n+ 1) =НОД(18n+ 1,12n+ 1) = =НОД(12n+ 1, 6n) = НОД(6n, 1) = 1.

Задача 3. Найдите НОД(111...111, 11... 11) - в записи первого числа 100 еди­ниц, в записи второго — 60.

Решение

НОД(111...111, 11... 11)= НОД(11...11, 1... 1)= НОД(1...1, 1...1)=

100 60 60 40 40 20

= НОД(1...1, 1...1)= 1...1

20 20 20

Ответ:1…1 – 20единиц

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

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

А, ведь знание их значительно упрощает процесс многих вычислений, экономит время, позволяет решать олимпиадные задачи. С решениями некоторых задач на применение основной теоремы арифметики, нахождения остатков, применения алгоритма Евклида для нахождения НОК и НОД своей работы я ознакомил старшеклассников, которые хотят получить высокие баллы на экзаменах по математике. Собранный мной материал можно использовать на уроках математики, на занятиях математического кружка.

Цель работы достигнута, задачи реализованы.

1. Список литературы и Интернет-ресурсов

1. Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки Киров: "АСА" 1994

2. http://fb.ru/article/202586/chto-takoe-arifmetika-osnovnaya-teorema-arifmetiki-dvoichnaya-arifmetika

3. http://www.problems.ru/view_by_source_

4. https://docviewer.yandex.ru/?url=http%3A%2F%2Fmathus.ru%2Fmath%2Fostear.pdf&name=ostear.pdf&lang=ru&c=589c0e534770

5. http://www.cleverstudents.ru/divisibility/nod_finding.html

Приложение 1

Решения задач раздела «Важные определения»

Задача 1. pи q - различные простые числа. Сколько делителей у числа:

a) pq; б) p²q; в) p²q²; г) pⁿq^m?

Решение

а) p и q простые числа, которые делятся на 1 и на самих себя, поэтому pq делится на 1, на p, на q и на pq (4 делителя)

б) p²q делится на 1, p, p², q, pq, p²q (6 делителей)

в) p²q² делится на 1, p, p², q, q², pq, p²q, pq², p²q² (9 делителей)

г) pⁿq^m делится на 1, p, p², .., pⁿ (n+1 делителей) и

делится на 1, q, q², q³,…, q^m (m+1 делителей). Всего делителей (n+1) • (m+1).

Ответ: а) 4, б) 9, в) n+1, г) (n+1) • (m+1).

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

Решение

Среди этих трёх чисел есть хотя бы одно чётное число. Значит, в разложении произведения на простые множители есть множитель 2. Среди этих трёх чисел одно число делится на 3. Значит, в разложении произведения на простые множители есть множитель 3. В разложении произведения на простые множители есть простые числа 2 и 3. Значит, оно делится на их произведение, то есть на 6.

Если же из этих трёх чисел чётное число само и является кратным 3, то это число автоматически делится на 6, поскольку оно кратно и 2 и 3 одновременно. Произведение такого числа на два рядом стоящих тоже будет кратно 6.

Задача 3. Докажите, что произведение любых пяти последовательных чисел делится: а) на 30; б) на 120.

Решение

а) Среди этих чисел есть число, кратное 3, есть число, кратное 5, и есть чётное число. Значит, произведение делится на произведение простых чисел 2, 3, 5, то есть на 30.

б) Среди пяти подряд идущих чисел есть два чётных, одно из которых делится на 4. Поэтому, в разложении произведения на простые множители число 2 встретится трижды. Значит, произведение делится на 3, 5 и 8, то есть и на их произведение 120.

Задача 4. р - простое число. Сколько существует натуральных чисел:

а) меньших р и взаимно простых с ним; б) меньших р² и взаимно простых с ним?

Например. Заметим, что 849 = 29² и 29 – простое число. Теперь нетрудно сообразить, что существует 29(29 - 1) = 812 натуральных чисел, которые не превосходят число 841 и не имеют с ним общих делителей, отличных от 1.

Ответ: а) p–1; б) p²– p.

Задача 5. Каково наименьшее натуральное п, такое, что п! делится на 990?

Решение

990 =2• 3•3•5•11

Поскольку в разложение числа 990 на простые множители входит число 11, то n≥ 11. С другой стороны, n= 11 удовлетворяет условию задачи. Это легко проверить 11!= 1•2•3•4•5•6•7•8•9•10•11= (2•5•9•11) •(1•3•4•6•7•8•10)

Ответ: n= 11.

Задача 6. Может ли n! оканчиваться ровно на 5 нулей?

Решение

24!=1•2•3•4•5•6•7•8•9•10•11•12•13•14•15•16•17•18•19•20•21•22•23•24 оканчивается на четыре нуля (2•5; 10; 12•15; 20). При добавлении множителя 25 добавится еще два нуля (так как число 25 в разложение факториала добавит сразу две пятерки, а именно, 25•4). Поэтому 25! оканчивается уже на шесть нулей.

Ответ: не может.

Задача 7. На сколько нулей оканчивается число 100! ?

Решение

В образовании нулей участвуют числа, кратные 2 и 5. Четных чисел больше, так что их не считаем. А чисел, кратных 5 от 1 до 100 - 20 штук. И еще 4 числа, кратных 25. Значит, нулей в результате будет 24.

Ответ: 24

Задача 8. Докажите, что число, имеющее нечетное число делителей, - точный квадрат.

Подсказка

Если d - делитель числа n, то ⁿ/_d – также делитель.

Решение

Если d - делитель числа n, то ⁿ/_d – также делитель. Таким образом, все делители числа делятся на пары. Если число имеет нечётное число делителей, то делители какой-то пары совпадают. Тогда d = n/d, откуда n=d², то есть число n – квадрат целого числа.

Из решения ясно, что нечётное число делителей имеют точные квадраты и только они.

Задача 9. Вася написал на доске пример на умножение двух двузначных чисел, а затем заменил в нем все цифры на буквы, причем одинаковые цифры - на одинаковые буквы, а разные - на разные. В итоге у него получилось АВВГ=ДДБЕ. Докажите, что он где-то ошибся.

Подсказка

Рассмотрите делимость на 11.

Решение

Результат умножения (число справа) делится на 11. Значит, на 11 делится один из множителей. Двухзначное число кратно 11, если равны его цифры. Но по условию A ≠ Б, В ≠ Г, что противоречит условию.

Задача 10. Может ли число, записываемое при помощи 100 нулей, 100 единиц и 100 двоек, быть точным квадратом?

Подсказка

Рассмотрите делимость на 3.

Решение

Согласно признаку делимости, такое число кратно 3. Если бы оно было полным квадратом, то делилось бы на 9. Но число не кратно 9 (сумма его цифр – 300 –не кратна 9).

Ответ: не может.

Задача 11. 56а = 65b. Докажите, что a+b - составное число.

Подсказка

Выразите a + b через a.

Решение

65(a + b) = 65a + 65b = 65a + 56a = 121a. Так как числа 65 и 121 взаимно просты, то a + b делится на 121. Поскольку 121 - составное число, то и a + b – составное.

Задача 12. Решите в натуральных числах уравнения:

а) х² — у² = 31; б) х² — у² = 303.

Решение

а) х² — у² = 31

(x +y) • (x-y) =31•1Получаем две системы:

Ответ: х=16, у=15

б) х² — у² = 303 303= 1•303 = 3•101

Получаем четыре системы:

Ответ: х=152, у=151 или х=52, у=49

Задача 13. Решите в уравнение х³ + х² + х — 3 = 0 в целых числах

Решение

х³ + х² + х — 3 = 0

х ( х² + х+1)=3

Значит х=±3или х=±1 Проверяем х=1

Ответ: х=1

Задача 14. Докажите, что для любых натуральных чисел а и b верно равенство НОД(а,b)НОК(а,b) = аb.

Решение

Из определения НОД следует, что a = a' НОД(a, b), b = b' НОД(a, b), где НОД(a', b') = 1. Из определения НОК следует, что

НОК(a, b) = a' b' НОД(a, b). Поэтому

НОД(a, b)НОК(a, b) =a' b'НОД(a, b)НОД(a, b) = ab.

Приложение 2

Решения задач раздела «Остатки»

Задача 3. 1) Докажите, что n⁵+4n делится на 5 при любом натуральном n.

Решение

n⁵+4n = n(n⁴+4) = n((n²)²+4)

Если n делится на 5, то и n⁵+4n = n(n⁴+4) тоже делится на 5.

Пусть n не делится на 5. Тогда n²оканчивается одной из цифр 1, 4, 6, 9,

а (n²)²оканчивается либо 1, либо 6,

поэтому (n⁴+4) оканчивается либо 5, либо 0, значит, делится на 5.

Задача 4. Докажите, что п² + 1 не делится на 3 ни при каком натуральном п.

Случай, когда n делится на 3, очевиден, п² + 1 не делится на 3 ни при каком натуральном п.

Если же не n делится на 3, то на 3 делится число n²– 1=(n–1)(n+1), поскольку одно из чисел n– 1, n+ 1 делится на 3. Следовательно, в этом случае

n²+ 1 ≡ 2 (mod 3).

Задача 5. Докажите, что п ³ + 2 не делится на 9 ни при каком натуральном п.

Решение

Случай, когда n делится на 3, очевиден. Если же не n делится на 3, то n= 3k ± 1 и n³ = (3k ± 1)³ = 27k³± 27k²+ 9k± 1 ≡ ± 1 (mod 9).

Задача 6. Докажите, что п³ — п делится на 24 при любом нечетном п.

Подсказка

Докажите, что указанное число делится и на 3, и на 8.

Решение

n³–n= n (n– 1)(n+ 1). Из трёх последовательных чисел одно делится на 3.

n– 1 и n+ 1 – последовательные чётные числа. Поэтому одно из них не только чётно, но и делится на 4. Значит, всё произведение делится на 2·4·3 = 24.

Задача 7.

а) Докажите, что p²–1 делится на 24, если p – простое число и p3

Решение

p²–1= (р - 1)(р + 1). Т.к. p – простое число и p3, то р – нечетное число. Известно, что среди трех последовательных чисел всегда найдется число кратное 3 и 4 (например, 6, 7, 8), если среднее число нечетно. Рассмотрим три последовательных числа р – 1, р, р + 1. р – нечетное число, значит, р – 1 и р + 1 – четные числа. р не кратно 3, значит, либо р – 1, либо р + 1 кратно 3, а так как оно четное, то кратно 6, другое число кратно 4, тогда произведение

(р - 1)(р + 1) кратно 24.

б) Докажите, что р² —q² делится на 24, если р и q - простые числа, большие 3.

Решение

p²–q²= (p–q)(p+q). p – q и p + q – чётные числа, причём их разность 2q не кратна 4. Значит, одно из этих чисел делится на 4. 2q также не кратно 3, значит, p – q и p + q дают разные остатки при делении на 3. Если бы ни одно из этих чисел не было кратно 3, то сумма (p – q) + (p + q) = 2p делилась бы на 3. Но это не так. Поэтому (p – q)(p + q) делится на 2·4·3 = 24.

Задача 8. Натуральные числа х, у, z таковы, что х² + у² = z². Докажите, что хотя бы одно из этих чисел делится на 3.

Решение

Если ни x, ни y не делятся на 3, то x² и y² дают остаток 1 при делении на 3 (см. решение задачи 4). Таким образом, их сумма имеет остаток 2 при делении на 3. Но z²не может иметь такого остатка. Значит наше предположение не верно, и либо x, либо y делится на 3

Задача 9. Докажите, что сумма квадратов трех натуральных чисел-, уменьшенная на 7, не делится на 8.

Подсказка

Выясните возможные остатки квадратов при делении на 8.

Решение

Квадрат при делении на 8 может дать остаток 0, 1 или 4. Число 7 нельзя представить как сумму трёх таких слагаемых.

Задача 12. Найдите остаток от деления 2¹⁰⁰ на 3.

Решение

При делении любого числа (не кратного 3) на 3 получаются остатки 1 или 2.

Рассмотрим степени 2 и остатки при делении на 3

2¹=2

2²=4 ост 1

2³=8 ост 2

2⁴=16_ ост 1

2⁵=32 ост 2

2⁶=64 ост 1

2⁷=128 ост 2

2⁸=256 ост 1

2⁹=512 ост 2 т.е. у четных степеней ост 1, а у нечетных ост 2

и т.д. 2¹⁰⁰ =…6 ост 1

Ответ: Ост. 1

Задача 13. Найдите остаток от деления З¹⁹⁸⁹ на 7.

Решение

3¹⁹⁸⁹ = 27⁶⁶³ ≡ (–1)⁶⁶³ = –1 (mod 7).

Ответ: 6.

Задача 14. Докажите, что 2222^555S + 55 55²²²² делится на 7.

Решение

5555 ≡ 4 (mod 7). Заметим, что 4³≡ 1 (mod 7),  значит, 2222⁵⁵⁵⁵+ 5555²²²²≡ 2222⁵⁵⁵⁵+ 5555⁵⁵⁵⁵, а это число делится на 2222 + 5555 = 7777.

Задача 15. р и р² + 2 - простые числа. Докажите, что р³ + 2 - также простое число.

Подсказка

Рассмотрите остатки от деления на 3.

Решение

Если число p делится на 3 и больше 3, то оно не простое. Пусть p не делится на 3 и больше 1. Тогда p² даёт остаток 1 от деления на 3, то есть p²+2 делится на 3. Поскольку p²+ 2 3, то это число – составное. Остаётся единственная возможность p= 3. При этом p³+ 2 = 29.

Задача 16. Докажите, что а³ + Ь³ + 4 не является кубом целого числа ни при каких натуральных а и Ь.

Подсказка

Выясните, какой остаток может давать число a³+b³+ 4 от деления на 9.

Решение

Куб может давать только остатки 0 или ±1 при делении на 9. Поэтому a³+b³+4 имеет остаток 0, 2, 3, 5 или 6, что не совпадает с остатками кубов.

Задача 17. Докажите, что число 6п³ + 3 не является шестой степенью целого числа ни при каком натуральном п.

Подсказка

Выясните, какой остаток может давать число 6n³+ 3 от деления на 7.

Решение

Куб может давать только остатки 0 или ±1 при делении на 7, а шестая степень – только остатки 0 и 1. 6n³+ 3 ≡ 3 –n³≡ 3, 2 или 4 (mod 7).