Делимость. Остатки. Принцип Дирихле.

В этом листке все числа натуральные (принадлежат множеству N).

Напоминаем:  Определение 4.0 a делится на b, если существует такое cN, что a = b * c (говорят, что b - делитель a). Обозначение - c = a / b.

  1. Верно ли, что выражения a + b, a - b (a b) , a * b, a2, ab делятся на c, если:

    a). a и b делятся на c     b). a и b не делятся на c    c). a делится на c, b не делится на c

  2. Вывести признаки делимости :

    a). на 2    b). на 5    c). на 3     d). на 9

Определение 4.1 a разделено на b>0 с остатком, если a представлено в виде (b * q) + r, 0r < b. В этом случае q называется неполным частным, а r - остатком от деления a на b.

  1. Докажите, что любое число можно разделить на любое другое (не равное 0) с остатком, причем единственным образом.
  2. a дает r в остатке при делении на c, b дает s в остатке при делении на c. Разделите с остатком выражения a + b, a - b, a * b, a2 на c. При c = 3, c = 4 для каждого из выражений заполните таблицу зависимости искомого остатка от r и s.
  3. Доказать, что произведение двух последних цифр квадрата натурального числа четно.
  4. Найти остаток от деления 3n2 + 8n + 5 на n при всех n.

Определение 4.2 Принцип Дирихле для кроликов состоит в том, что если k + 1 кроликов сидят в k клетках, то по крайней мере в одной клетке сидит не менее двух кроликов.

  1. Доказать, что среди любых 20 последовательных чисел найдутся 3, делящиеся на 6.
  2. Доказать, что среди любых 4 чисел можно выбрать 2 так, чтобы их сумма либо разность делилась на 5.
  3. Переформулировать принцип Дирихле для a кроликов и b клеток, где a = q * b + r, 0r < b.

Определение 4.3 p > 1 называется простым числом, если оно имеет ровно два делителя (себя и единицу). Прочие числа, большие 1, называются составными.

  1. Найти все простые числа p такие, что:
    a). p + 1 простое    b). p2 + 1 простое    c). p2 - 1 простое.
  2. Доказать, что если (m-1)! + 1 делится на m, то m - простое число.

Определение 4.4 Наибольшим общим делителем чисел a и b называется наибольший из делителей и a, и b (он обозначается НОД(a,b)). Наименьшим общим кратным чисел a и b называется наименьшее из чисел, имеющее a и b своими делителями (обозначается НОК(a,b)). a и b взаимно просты, если НОД(a,b) = 1.

  1. Доказать, что n и n+1 взаимно просты.
  2. Доказать, что для любого n существуют n подряд идущих составных чисел.
  3. Доказать или опровергнуть, что при любом n число n2+41n+41 простое.
  4. Доказать или опровергнуть, что простых чисел бесконечно много.
  5. Про НОД и НОК
    a). доказать, что a / НОД(a,b) и b / НОД(a,b) взаимно просты.
    b). доказать, что если с является делителем a и b, то c делит НОД(a,b).
    c). a и b взаимно просты. Найти НОК(a,b).
    d). доказать, что a * b = НОД(a,b) * НОК(a,b).
    e). найти НОК(2, 3, ..., 20) (наименьшее общее кратное 19 чисел).

[Вернутся к оглавлению]