Для каждого натурального n обозначим через P(n) число разбиений n в сумму натуральных слагаемых (разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми; например,  P(4) = 5,  потому что  4 = 4 = 1 + 3 = 2 + 2 = 1 + 1 + 2 = 1 + 1 + 1 + 1  – пять способов).
  а) Количество различных чисел в данном разбиении назовем его разбросом (например, разбиение  4 = 1 + 1 + 2  имеет разброс 2, потому что в этом разбиении два различных числа). Докажите, что сумма Q(n) разбросов всех разбиений числа n равна   1 + P(1) + P(2) + ... + P(n–1).
  б) Докажите, что  

   Решение

Темы:    [ Арифметика остатков (прочее) ] [ Китайская теорема об остатках ]

Сложность: 3 Классы: 6,7,8

Прислать комментарий

Условие

a ≡ 68 (mod 1967),   a ≡ 69 (mod 1968).  Найти остаток от деления a на 14.

Решение

1967 = 7·281.

Первый способ. Заметим, что  a + 1899  делится и на 1967 и на 1968, то есть делится на 14.  1899 ≡ 9 (mod 14),  поэтому  a + 9  делится на 14, то есть
a ≡ 5 (mod 14).

Второй способ. Из первого сравнения следует, что  a ≡ 5 (mod 7),  а из второго – что a нечётно. Следовательно,  a ≡ 5 (mod 14).

Ответ

5.

Источники и прецеденты использования