Деление с остатком
Простое число
Наибольший общий делитель
Наименьшее общее кратное
Признак делимости на 2 и на 5
Признак делимости на 4
Признак делимости на 3 и на 9
Признак делимости на 6
Оглавление
Предметный указатель
Литература

§1. Натуральные и целые числа

   Числа 1, 2, 3, …, появившиеся в результате счета, называются натуральными числами. Совокупность чисел 0, ±1, ±2, ±3, … образует множество всех целых чисел.
   Над целыми числами устанавливаются действия сложения и умножения, которые обладают следующими основными свойствами.
  1. Переместительное свойство сложения:a + b = b + a (Буквы a, b, c, … обозначают целые числа).
  2. Сочетательное свойство сложения: (a + b) + c = a + (b + c)
  3. Переместительное свойство умножения: a · b = b· a
  4. Сочетательное свойство умножения: (a · b)· c = a · (b · c)
  5. Распределительное свойство, связывающее сложение и умножение:(a + b)· c = a·c + b·c.
   Основные свойства (законы арифметики) остаются справедливыми для любого конечного числа слагаемых и сомножителей.
   Полагают а + 0 = a, a·0 = 0 при всех а.
   Вычитание и деление определяются как действия, обратные сложению и умножению.
   Число с называется разностью чисел а и b,
с = а - b,
если b + c = a. Вычитание всегда выполнимо и единственно, т. е. для любых а и b существует и притом единственная разность с.
   Число q называется частным от деления а на b,
q = a : b или ,
если b·q = a.Деление не всегда выполнимо в множестве целых чисел.
   Невозможно деление на нуль. Если а ≠ 0, а b = 0, то, очевидно, нет такого q, для которого b·q = a. Если a = b = 0, то q - любое. Поэтому деление на нуль не определено.
   Если для чисел а и b существует частное q, т. е. b·q = a, то говорят, что а делится на b (или b делит а). При этом а называется кратным числа b (или делимым), a b – делителем числа а. Число называется четным, если оно делится на 2, и нечетным в противном случае. Нуль - четное число.
   Для любых чисел а и b (b > 0) справедливо следующее утверждение: число а всегда можно представить и притом единственным образом в виде
a = b·q + r, где 0 ≤ r < b                     (1)
Очевидно, что всякое целое число а представимо в виде (1). Покажем единственность такого представления.
   Допустим, что a = b·q + r и также a = b·q1 + r1 , где 0 ≤ r < b и 0 ≤ r1 < b. Тогда
0 = b·(q1 - q) + (r1 - r)
и, следовательно, число r1 - r делится на b. Так как 0 ≤ r < b и 0 < r1 < b, то это возможно только при r1 - r = 0, т.е. при r1 = r. Отсюда вытекает, что и q1 = q. Утверждение доказано.
   Представление числа а в виде (1) называется делением числа а на число b (b > 0) с остатком. При этом q называется неполным частным, а r - остатком от деления а на b. Для натуральных чисел вводятся понятия простого и составного числа.
   Определение. Натуральное число, не равное единице, называется простым, если оно делится только на себя и на единицу. Натуральное число, отличное от единицы и не являющееся простым, называется составным.
   Единица - единственное число, которое не является ни простым, ни составным.
   Доказано, что всякое натуральное число, большее единицы, можно представить в виде произведения простых сомножителей и притом единственным способом (произведения, отличающиеся только порядком сомножителей, различными не считаются). Объединяя равные сомножители, получим
                     (2)
где p1, p2, …, pn - различные простые делители числа а, а α1, α2 , …, αn - число их повторений в разложении числа а. Представление (2) называется каноническим разложением натурального числа на простые сомножители.
   Например, 72 = 23·32, 17 = 171. Если , то любой натуральный делитель а имеет вид
                     (3)
где 0 ≤ β1≤ α1, 0 ≤ β2≤ α2, …, 0 ≤ βn≤ αn (равенство βk = 0 означает, что соответствующее основание pk не содержится в разложении числа d).
   В самом деле, пусть d делит а. Тогда a = d·q. У чисел d и q могут оказаться равными их простые делители. Поэтому все простые делители числа d входят в каноническое разложение числа а с показателями, не меньшими тех, с которыми они входят в каноническое разложение d. Следовательно, d имеет вид (3), что и утверждалось.
   Обратно, всякое число вида (3), очевидно, делит а.
   Пример I. Показать, что число различных положительных делителей числа (включая 1 и а) равно произведению
(α1 + 1)·(α2 + 1)·…·(αn + 1).
   Решение. Каждый делитель числа а имеет вид (3), где α1 принимает α1 + 1 значений: 0, 1, 2, …, α1; β2 независимо от β1 принимает α2 + 1 значений: 0, 1, 2, ..., α2 и т.д. Каждой такой комбинации β1, β2, …, βn соответствует один делитель числа а, причем различным комбинациям соответствуют различные делители (в противном случае у одного и того же числа существовали бы различные канонические разложения, что невозможно).
   Число всех таких комбинаций, а значит и делителей числа а, равно произведению (α1 + 1)·(α2 + 1)·…·(αn + 1).
   Например, число различных делителей 72 = 23·32 равно (3 + 1)·(2 + 1) = 12. Каждый делитель 72 имеет вид , где β1 = 0, 1, 2, 3; β2 = 0, 1, 2. Придавая β1 и β2 эти значения, получим все различные положительные делители числа 72:
1, 2, 4, 8; 3, 6, 12, 24; 9, 18, 36, 72.
   Определение. Всякое число, делящее одновременно числа a, b, … ,l, называется их общим делителем. Наибольший из общих делителей называется наибольшим общим делителем и сокращенно обозначается НОД или символом (а,b, …, l). Если (а,b, …, l) = 1 , то числа а,b, …, l называются взаимно простыми.
   Например, числа 6, 8, 15 взаимно простые, так как (6, 8, 15) = 1.
   Всякое число, которое делится на каждое из чисел а, b, …, l называется их общим кратным. Наименьшее положительное общее кратное называется наименьшим общим кратным и сокращенно обозначается НОК.
   Например, для чисел 24 и 36 НОД = 12, НОК = 72. Справедливы следующие свойства взаимно простых чисел.
  1. Если число а делится на каждое из взаимно простых чисел, то оно делится и на произведение этих чисел. Например, если число делится на 3 и на 5 ((3, 5) = 1), то оно делится и на 15. Однако нельзя утверждать, что число, делящееся на 4 и на 6 ((4, 6) ≠ 1), обязательно делится и на 24. Например, это неверно для 36.
  2. Если произведение a·b делится на с, где b и с - взаимно простые числа, то а делится на с.
   Найдем НОД и НОК чисел а и b. С этой целью запишем их канонические разложения:
, ,
где некоторые из αk и βk могут обращаться в нуль.
Согласно формуле (3) любой общий делитель чисел а и b имеет вид
,                     (4)
где каждое γk не превосходит чисел αk и βk.
   Полагая в разложении (4) каждое γk равным наименьшему из чисел αk и βk, получим наибольший общий делитель чисел а и b.
   Очевидно, число вида (4) будет делиться одновременно на а и b, если в качестве каждого γk принять наибольшее из чисел αk и βk. Оно является наименьшим натуральным числом, делящимся на а и b, т.е. является НОК чисел а и b. Аналогично находятся НОД и НОК чисел а, b, …, l.
   Пример 2. Найти НОД и НОК чисел 72 и 60.
   Решение. Запишем для данных чисел их канонические разложения:
72 = 23·32, 60 = 22·3·5,
тогда НОД = 22·3 = 12, НОК = 23·32·5 = 360.
   Из самого способа нахождения НОД и НОК вытекают следующие их свойства:
  1. НОД чисел а и b делится на любой их общий делитель.
  2. .
   Практически при разложении числа на множители и нахождении НОД и НОК пользуются признаками делимости. Признаком делимости числа а на некоторое число b называется необходимое и достаточное условие делимости а на b.
   Пусть N-делимое. В десятичной системе счисления натуральное число N записывается в виде
N = an·10n + an-1·10n-1 + … + a1 ·10 + a0,                     (5)
где a0 - число единиц, a1 - число десятков, a2 - число сотен и т.д.
   Рассмотрим признаки делимости на 2, 3, 4, 5, 6, 9.
   Признак делимости на 2 и на 5. На 2 (или на 5) делятся те и только те числа, цифра единиц которых выражает число, делящееся на 2 (или соответственно на 5).
   В самом деле, N = (an·10n + an-1·10n-1 + … + a1·10)+ a0. В скобках стоит число, кратное 10, и оно делится на 2 и на 5. Поэтому для делимости N на 2 (или на 5) необходимо и достаточно, чтобы на 2 (или соответственно на 5) делилось a0.
   Признак делимости на 4. На 4 делятся те и только те числа, у которых две последние цифры выражают число, делящееся на 4.
   Утверждение вытекает из записи делимого в виде
N = (an·10n + an-1·10n-1 +…+ a2· 102) + (a1·10 + a0).
   Признак делимости на 3 и на 9. На 3 (или на 9) делятся те и только те числа, сумма цифр которых делится на 3 (или соответственно на 9).
   Для доказательства запишем делимое в виде
N = [an·(10n - 1) + an-1·(10n-1 - 1) + … + a1·(10 - 1)]+ (an + an-1 + … +a0)
Очевидно, что число
делится на 3 и на 9. Поэтому для делимости N на 3 или на 9 необходимо и достаточно, чтобы число, стоящее в круглых скобках и равное сумме цифр числа N, делилось на 3 или на 9.
   Признак делимости на 6. На 6 делятся те и только те числа, которые одновременно делятся на 2 и на 3. Это следует из свойства делимости числа на произведение взаимно простых чисел.
   Отметим следующее свойство последовательных чисел. Из n последовательных целых чисел
a, a + 1, … , a + n - 1                     (6)
одно и только одно делится на n.
   Действительно, если a = n·q, то утверждение справедливо.
   Пусть a = n·q + k, где k одно из чисел
1, 2, … , n - 1.
Тогда число а + (n - k) = n·q + k + (n - k) = n·(q + 1) находится среди чисел (6) и делится на n.
   Среди чисел (6) нет других чисел, делящихся на n, так как в противном случае разность таких чисел, меньшая n, делилась бы на n, что невозможно.
   Например, число n³ - n = (n - 1)·n·(n + 1) делится на 2, на 3, и, следовательно, на 6.