Разделы 
Дополнительно
Простые и составные числа. Признаки делимости.
частное
делитель числа
кратное число
четное число
нечетное число
простое число
составное число
Признак делимости на 2
Признак делимости на 4
Признак делимости на 5
Признак делимости на 3 и 9
Если $a$ и $b$ - натуральные числа, причем$a=bq$,
где $q$ - также натуральное число, то говорят, что $q$ -
частное от деления числа $a$ на число $b$, и пишут: $q = a/b$.
Также говорят, что $a$ делится на $b$ нацело или без остатка. Всякое число $b$, на которое $a$ делится без остатка, называется делителем числа $a$
. Само число $a$ но отношению к своему делителю называется кратным
. Таким образом, числа, кратные $b$, суть числа $b, 2b, 3b, \cdots$.Числа, кратные числу 2 (т. е. делящиеся на 2 без остатка), называются четными
. Числа, не делящиеся на 2 нацело, называются нечетными
. Каждое натуральное число либо четно, либо нечетно. Если каждое из двух чисел $a_{1}, a_{2}$ является кратным числа $b$, то и сумма $a_{1}+a_{2}$ - кратное числа $b$. Это видно из записи $a_{1}=bq_{1}, a_{2}=bq_{2}; a_{1}+a_{2}=bq_{1}+bq_{2}= b (q_{1}+q_{2})$.
Обратно, если $a_{1}$ и $a_{1}+a_{2}$ - кратные числа $b$, то $a_{2}$ - также кратное числа $b$.
Всякое отличное от единицы натуральное число имеет по меньшей мере два делителя: единицу и самоё себя.
Если число не имеет никаких других делителей, кроме себя и единицы, оно называется простым
. Число, имеющее какой-нибудь делитель, отличный от себя и единицы, называют составным
числом. Единицу принято не относить ни к простым, ни к составным числам. Вот несколько первых простых чисел, записанных в порядке возрастания: $2,3,5,7,11,13,17, \cdots$
Число 2 - единственное четное простое число; все остальные простые числа - нечетные.
То, что простых чисел имеется бесконечное множество, было установлено еще в древности (Евклид, III век до нашей эры).
Идея доказательства Евклида бесконечности множества простых чисел весьма проста. Допустим, что простых чисел - конечное число; перечислим их все, например, расположив в порядке возрастания:
$2,3,5, \cdots , p$. (1)
Составим число, равное их произведению плюс единица:
$a = 2 \cdot 3 \cdot 5 \cdots p+1$.
Очевидно, что это число не делится ни на одно из чисел (1). Следовательно, либо оно само является простым, либо, если оно составное, то имеет простой делитель, отличный от чисел (1), что противоречит допущению о том, что в записи (1) перечислены все простые числа.
Это доказательство представляет большой интерес, так как дает пример доказательства теоремы существования (бесконечного множества простых чисел), не связанного с фактическим отысканием объектов, существование которых доказывается.
Можно доказать, что всякое составное число представимо в виде произведения простых чисел. Так, например, $2,3,5, \cdots , p$. (1)
Составим число, равное их произведению плюс единица:
$a = 2 \cdot 3 \cdot 5 \cdots p+1$.
Очевидно, что это число не делится ни на одно из чисел (1). Следовательно, либо оно само является простым, либо, если оно составное, то имеет простой делитель, отличный от чисел (1), что противоречит допущению о том, что в записи (1) перечислены все простые числа.
Это доказательство представляет большой интерес, так как дает пример доказательства теоремы существования (бесконечного множества простых чисел), не связанного с фактическим отысканием объектов, существование которых доказывается.
$1176 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 7 \cdot 7$ или $1176 = 2^{3} \cdot 3 \cdot 7^{2}$.
Как видно из этого примера, в разложении данного числа на простые множители некоторые из них могут повторяться несколько раз.
В общем случае в записи разложения числа $a$ на простые множители
$a = p^{k_{1}}_{1} p^{k_{2}}_{2} \cdots p^{k_{n}}_{n}$ (2)
подразумевается, что все простые числа $p_{1},p_{2}, \cdots , p_{n}$ различны между собой (причем $p_{1}$ повторяется множителем $k_{1}$ раз, $p_{2}$ повторяется множителем $k_{2}$ раз и т. д.). При этом условии можно доказать, что разложение единственно с точностью до порядка записи сомножителей.
При разложении числа на простые множители полезно бывает использовать признаки делимости, позволяющие выяснить, делится ли данное число на некоторое другое число без остатка, не производя самого деления. Мы выведем признаки делимости на числа 2, 3, 4, 5, 9.
1.
Признак делимости на 2. На 2 делятся те и только те числа, в записи которых последняя цифра выражает четное число (0, 2, 4, 6 или 8).
Доказательство. Представим число $\overline{c_{1}c_{2} \cdots c_{m}}$ в виде $\overline{c_{1}c_{2} \cdots c_{m}} = \overline{c_{1}c_{2} \cdots 0} + c_{m}$.Первое слагаемое в правой части делится на 10 и потому - четное; сумма будет четной тогда и только тогда, когда $c_{m}$ - четное число.
2.
Признак делимости на 4 Число $\overline{c_{1}c_{2} \cdots c_{m}}$ делится на 4 тогда и только тогда, когда двузначное число, выражаемое его последними двумя цифрами, делится на 4.
Доказательство. Представим число $\overline{c_{1}c_{2} \cdots c_{m}}$ в виде$\overline{c_{1}c_{2} \cdots c_{m}} = \overline{c_{1}c_{2} \cdots 00} + \overline{c_{m-1}c_{m}}$
Первое слагаемое делится на 100 и тем более на 4. Сумма будет делиться на 4 в том и только в том случае, если $\overline{c_{m-1}c_{m}}$ делится на 4.
3.
Признак делимости на 5. На 5 делятся те и только те числа, запись которых заканчивается цифрой 0 или цифрой 5.
4. Признаки делимости на 3 и на 9. Число делится на 3 {соответственно на 9) в том и только в том случае, когда сумма его цифр делится на 3 (соответственно на 9).
Доказательство. Запишем очевидные равенства$10 = 9+1$,
$100 = 99 + 1$,
$1000 = 999+1$,
$ \cdots $,
в силу которых можно число $\overline{c_{1}c_{2} \cdots c_{m}}$ представить в виде
$a_{m}=c_{1}(99 \cdots 9 + 1) + \cdots + c_{m-1} (9+1) + c_{m}$
или
$a_{m}=c_{1} \cdot 99 \cdots 9 + \cdots + c_{m-1} \cdot 9 + (c_{1} + c_{2} + \cdots + c_{m-1} + c_{m})$.
Видно, что все слагаемые, кроме, быть может, последней скобки, делятся на 9 (и тем более на 3). Поэтому данное число делится на 3 или на 9 тогда и только тогда, когда делится на 3 или на 9 сумма его цифр $c_{1}+c_{2}+ \cdots + c_{m}$.
