I. Простые и составные числа. Каноническое разложение на множители.
Простыми называются натуральные числа, имеющие ровно два различных натуральных делителя – 1 и само число. Составными называются числа, являющиеся произведением нескольких простых. Единица не является ни простым, ни составным числом.
Каждое натуральное число, большее единицы является либо простым, либо составным, т.е. его можно представить в виде произведение простых чисел (возможно одного простого числа). Сгруппировав одинаковые простые числа, каждое такое число можно записать в виде n=p1a1p2a2…pnan(p1,p2,…pn – простые числа, запись ab означает произведение числа a самого на себя b раз). Такое представление называется каноническим разложением на множители. Для каждого натурального числа, большего единицы, существует только одно такое разложение. Данный факт называется «основная теорема арифметики». Разложения на множители полностью определяет свойства делимости числа, т.е. если число p – входит в разложение на простые множители, то число делиться на p.
1. Сколько существует простых чисел меньших 100?
2. Дано чётное число A. Верно ли, что 3A делиться на 6?
3. Докажите, что если числа a и b деляться на с, то a+b и a-b также деляться на с.
4. Докажите, что если разность двух чисел делиться на x, то эти числа имеют одинаковые остатки при делении на x.
5. Сумма всех простых делителей числа n равна 5, а сумма наибольших (для каждого простого делителя) степеней, на которые делиться n, равна 3. Найдите все возможные n.
6. Сколько делителей имеет число pk, где p – простое число.
7. Дано натуральное число n=p1a1p2a2…pnan, являющееся квадратом натурального числа. Докажите, что сумма a1+a2+…+an – чётная. (Для решения задачи необходимо знать, что ax·ay=ax+y).
8. Докажите, что если квадрат натуральное числа делиться на p – простое число, то он делиться и на p2. (Квадратом числа x называется число x2).
9. Найдите наименьшее n, при котором n! делиться на a)19; б)18.
10. На какое количество нулей оканчивается число 25!? (n!=1·2·3·…·(n-1)·n и читается «n факториал»).
II. НОК и НОД двух чисел. Взаимно простые числа.
НОК(a,b) – наименьшее общее кратное, т.е. наименьше число n такое, что каждое из чисел a и b делит n. НОД(a,b) – наибольший общий делитель, т.е. наибольшее число d такое, что каждое из чисел a и b делится на d.
Два числа a и b называются взаимно простыми, если НОД(a,b)=1, другими словами - если числа a и b не имеют общих делителей, отличных от 1.
1. Какие числа взаимно просты с 2?
2. Найдите НОД(n,n+1)? (См. задачу 3, пункт I.)
3. При каком условии для двух чисел a и b выполняется равенство a·b=НОК(a,b)?
4. Докажите, что a·b=НОД(a,b)·НОК(a,b).
5. Пусть число x делиться на 3 и на 5. Докажите, что оно делиться на 15.
6. Пусть число x делиться на 4 и на 6. Верно ли, что x делиться на 24? На какое число гарантировано делиться x?
7. Сколько существует чисел взаимно простых с a) простым число p; б) pn.
8. Коля, Серёжа и Ваня регулярно ходили в кинотеатр. Коля бывал в нём каждый 3-й день, Серёжа — каждый 7-й, Ваня — каждый 5-й. Сегодня все ребята были в кино. Когда все трое встретятся в кинотеатре в следующий раз?
III. Делимость.
1. Докажите, что число делиться на 5, если оно оканчивается на 0 или 5.
2. Докажите, что число делиться на 2 (на 4), если его последняя цифра (2 цифры) делится на 2 (на 4).
3. Докажите, что число делиться на 2n, если n его последних цифр делятся на 2n.
В следующих задачах необходимо знать, что если сумма цифр числа делится на 3(на 9), то и само число делиться на 3 (на 9).
4. Докажите, что число вида 11..1122..2200..00 (100 – единиц, 100 – двоек, 100 нулей) не может являться квадратом натурального числа.
5. У числа 2727…27 (27 записано 1000 раз) посчитали сумма цифр, получили число S. У числа S снова посчитали сумму цифр, получили число S1. У числа S1 посчитали сумму цифр и т.д. В конце получили однозначное число. Какое это число? В данной задаче необходимо знать, что если сумма цифр числа делится на 3(на 9), то и само число делиться на 3 (на 9).
6. Делится ли число 102002 + 8 на 9?
Число делиться на 11, если разность суммы цифр, стоящих на чётных местах, и суммы цифр, стоящих на нечётных местах, делится на 11. Например, число 132242506 делится на 11, т.к. (1+2+4+5+6)-(3+2+2+0)=11 – делится на 11.
7. Вася написал на доске пример на умножение двух двузначных чисел, а затем заменил в нем все цифры на буквы, причем одинаковые цифры - на одинаковые буквы, а разные - на разные. В итоге у него получилось АБ × ВГ = ДДЕЕ. Докажите, что он где-то ошибся.
8. Незнайка хвастал своими выдающимися способностями умножать числа "в уме". Чтобы его проверить, Знайка предложил ему написать какое-нибудь число, перемножить его цифры и сказать результат. "1210", — немедленно выпалил Незнайка. "Ты неправ!" — сказал, подумав, Знайка. Как он обнаружил ошибку, не зная исходного числа?
IV. Остатки. Перебор остатков.
1. Найдите все числа, при делении которых на 7 в частном получится то же число, что и в остатке.
2. Доказать, что остаток от деления простого числа на 30 - простое число или единица.
3. Докажите, что среди двух (трёх) подряд идущих натуральных чисел, найдётся число, делящееся на 2 (на 3).
4. Докажите, что число вида (x+1)(x+2)(x+3) делиться на 6.
5. Докажите, что среди k подряд идущих натуральных чисел, найдётся число, делящееся на k.
6. Докажите, что среди k+1 подряд идущих натуральных чисел, найдётся два числа, имеющие одинаковые остатки при делении на k.
7. Какие остатки может иметь число n2 при делении на 3, на 4.
8. Даны три натуральных числа x,y,z, для которых выполняется условие x2+y2=z2. Докажите, что одно из чисел x,y,z делиться на 3.
9. Докажите, что n 3 + 2 n делится на 3 для любого натурального n.
10. Найдите наибольшее десятизначное число, составленное из различных цифр, такое, что сумма любых трёх подряд идущих цифр делится на 3.
11. Найдите последнюю цифру числа 92014.
12. Делится ли число 102002 + 8 на 9?