.:Делимость и Остатки:. Простые и составные числа. Основная теорема арифметики. Взаимно простые числа. НОД. НОК. Алгоритм Евклида. Сумма двух натуральных чисел и сумма их остатков. Произведение двух натуральных чисел и произведение их остатков.

Простые и составные числа –Число является составным, если оно равно произведению двух меньших натуральных чисел. В противном случае число называется простым. Единица не является ни простым, ни составным числом!

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

Упражнение В о п р о сО т в е т 1). Число А не делится на 3. Может ли на 3 делится число 2А? нет 2). Верно ли, что если натуральное число делится на 4 и 3, то оно делится на 12? да 3). Число А-чётно. Верно ли, что 3А делится на 6? да 4). Дано выражение: 2(в 9 степени), умноженное на 3. Делится ли оно на 2? да 5). Дано выражение: 2(в 9 степени), умноженное на 3. Делится ли оно на 9? нет А теперь расчертим данную таблицу и рассмотрим примеры:

О т в е т ы 1). Нет, поскольку тройка не входит в разложение на простые множители числа А 2). Да, поскольку в разложении на простые множители числа, делящегося на 4, двойка входит по крайней мере 2 раза; а т.к. число делится и на 3, то в его разложение входит и тройка. Поэтому оно делится на 12. 3). Верно, т.к. 2 и 3 входят в разложение числа 3А на простые множители. 4). Да, т.к. 2 входит в разложение этого числа на простые множители. 5). Нет, т.к. в разложение данного числа на простые множители тройка входит лишь один раз, а в разложение 9 – дважды.

Примечания: 1. Два простых числа являются взаимно простыми. 2. Если некоторое число делится на два взаимно простых числа n и m, то оно делится и на их произведение mn. 3. Если число p*A делится на q, где p и q взаимно просты, то и A делится на q. Взаимно простые числа Два числа наз. взаимно простыми, если у них нет общих делителей Н О Д двух чисел- наибольший из общих делителей этих чисел Н О К двух чисел- наименьшее число, делящееся на каждое из них

Теоремы Число, имеющее нечётное число делителей – точный квадрат. Для любых натуральных чисел А и В верно равенство: НОД(А,В) * НОК(А,В)=АВ

Алгоритм Евклида Алгоритм Евклида основан на: Любой общий делитель чисел А и В(А>В) делит также число А-В; кроме того, любой общий делитель чисел В и А-В делит число А. Тем самым, НОД(А,В)=НОД(В,А – В)

О с т а т к и Определение Утверждение Свойство Разделить натуральное число N на натуральное число m с остатком – означает предста- вить N в виде N=km+ r. r-остаток от деления. 1. Сумма любых двух натуральных чисел и сумма их остатков имеют одинаковый ос- татки при деле- нии на натураль- ное n. Квадрат любого натурального числа при делении на 3 и 4 будет давать в остатке 0 или единицу. 2. Произведение любых двух нат. чисел и произве- дение их остатков имеют одинако- вые остатки при делении на нату- ральное n.

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

О Т В Е Т Ы 1. При решении задачи необходимо док-ть, что любые два числа из этих семи дают одинаковый остаток при делении на 5. Для этого нужно рассмотреть две шестёрки: одну – не содержащую первое из них, вторую – не содерж. второе. 2. Предположим противное. Пусть p 1, p 2,…p n – все простые числа. Рассмотрим число p 1 * p n +1. Это число не делится ни на одно из чисел p 1, p 2,…,p n и, следовательно, не может быть разложено в произведение простых. Противоречие.

Надеюсь, что вы все усвоили данную тему. Применяйте свои знания при решении олимпиадных задач!