Делимость натуральных чисел

Отношение делимости. Если при делении с остатком натурального числа а на натуральное число b остаток равен 0, то говорят что а делится на b. В этом случае а называют кратным числа b, b называют делителем числа а.

Обозначение а∶b

Запись символами (а,bN) (а∶b)(сN) (а=вс).

Простое число. Натуральное число называют простым, если оно делится только на себя и на единицу, т.е если у него только два делителя.

Составное число. Натуральное число называют составным, если у него более двух делителей.

1 не является ни простым, ни составным числом, т.к имеет только один делитель – себя.

2 - единственное четное простое число.

Свойства отношения делимости:

1. если а делится на b, то а≥b.

2. рефлексивность, т.е. каждое натуральное число делится само на себя.

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

4. транзитивность, т.е. если первое число делится на второе число, второе число делится на третье число, то первое число делится на третье число.

Отношение делимости на N – это отношение частичного нестрогого порядка. Порядок частичный, т.к. есть такие пары разных натуральных чисел, ни одно из которых не делится на другое.

Признак делимости суммы на число. Если каждое слагаемое суммы делится на число, то вся сумма делится на это число (для того чтобы сумма делилась на число, достаточно, чтобы каждое слагаемое делилось на это число). Этот признак не является необходимым, т.е. если каждое слагаемое не делится на число, то вся сумма может делиться на это число.

Признак делимости разности на число. Если уменьшаемое и вычитаемое делятся на число и уменьшаемое больше вычитаемого, то разность делится на это число (для того чтобы разность делилась на число, достаточно, чтобы уменьшаемое и вычитаемое делились на это число, при условии, что эта разность положительна). Этот признак не является необходимым, т.е. уменьшаемое и вычитаемое могут не делиться на число, а их разность может делиться на это число.

Признак неделимости суммы на число. Если все слагаемые суммы, кроме одного, делятся на число, то сумма не делится на это число.

Признак делимости произведения на число. Если хотя бы один множитель в произведении делится на число, то произведение делится на это число (для того чтобы произведение делилось на число, достаточно, чтобы один множитель в произведении делился на это число). Этот признак не является необходимым, т.е. если ни один множитель в произведении не делится на число, то произведение может делиться на это число.

Признак делимости произведения на произведение. Если число а делится на число b, число с делится на число d, то произведение чисел а и с делится на произведение чисел b и d. Этот признак не является необходимым.

Признак делимости натуральных чисел на 2. Чтобы натуральное число делилось на 2, необходимо и достаточно, чтобы десятичная запись этого числа оканчивалась на одну из цифр 0, 2, 4, 6 или 8.

Признак делимости натуральных чисел на 5. Чтобы натуральное число делилось на 5, необходимо и достаточно, чтобы десятичная запись этого числа оканчивалась на 0 или на 5.

Признак делимости натуральных чисел на 4. Чтобы натуральное число делилось на 4, необходимо и достаточно, чтобы десятичная запись этого числа оканчивалась на 00 или две последние цифры в десятичной записи этого числа образовывали двузначное число, кратное 4.

Признак делимости натуральных чисел на 3. Чтобы натуральное число делилось на 3, необходимо и достаточно, чтобы сумма всех цифр десятичной записи этого числа делилась на 3.

Признак делимости натуральных чисел на 9. Чтобы натуральное число делилось на 9, необходимо и достаточно, чтобы сумма всех цифр десятичной записи этого числа делилась на 9.

Общий делитель натуральных чисел а и в - это натуральное число, которое является делителем каждого из этих чисел.

Наибольший общий делитель натуральных чисел а и в- это наибольшее натуральное число из всех общих делителей этих чисел.

Обозначение НОД (а, в)

Свойства НОД (а, в):

1. всегда существует и только один.

2. не превосходит меньшего из а и в.

3. делится на любой общий делитель а и в.

Общее кратное натуральных чисел а и в - это натуральное число, кратное каждому из этих чисел.

Наименьшее общее кратное натуральных чисел а и в – это наименьшее натуральное число из всех общих кратных этих чисел.

Обозначение НОК (а, в )

Свойства НОК (а, в):

1. всегда существует и только одно.

2. не меньше большего из а и в.

3. любое общее кратное а и в делится на него.

Взаимно простые числа. Натуральные числа а и в называют взаимно простыми, если у них нет общих делителей, кроме 1, т.е. НОД (а, в)=1.

Признак делимости на составное число. Чтобы натуральное число а делилось на произведение взаимно простых чисел m и n, необходимо и достаточно, чтобы число а делилось на каждое из них.

Примеры:

1. Чтобы число делилось на 12, необходимо и достаточно, чтобы оно делилось на 3 и на 4.

2. Чтобы число делилось на 18, необходимо и достаточно, чтобы оно делилось на 2 и на 9.

Разложение числа на простые множители- это представление этого числа в виде произведения простых множителей.

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

Алгоритм нахождения НОД:

Разложить каждое число на простые множители.

Записать произведение общих для данных чисел простых множителей, причем каждый

множитель записать с наименьшим показателем, с каким он входит во все разложения.

Найти значение полученного произведения. Это и будет НОД данных чисел.

Алгоритм нахождения НОК:

Разложить каждое число на простые множители.

Записать произведение всех простых множителей из разложений, причем каждый из них записать с наибольшим показателем, с каким он входит во все разложения.

Найти значение полученного произведения. Это и будет НОК данных чисел.