Заданы k различных взаимно простых натуральных чисел n1, n2, … nk и k натуральных чисел d1 < n1, d2 < n2,… dk < nk.
Требуется дать верхнюю оценку минимальному натуральному числу m, такому, что m%n1 ≠ d1, m%n2 ≠ d2, … m%nk ≠ dk.
Здесь a%b означает остаток от деления a на b.

Предыдущий
вопрос Следующий
вопрос

В общем случае, для нахождения верхней оценки минимального натурального числа m можно воспользоваться китайской теоремой об остатках.

Пусть n = n1n2…*nk. Тогда m%n будет остатком от деления m на n, а m%n1, m%n2, …, m%nk - остатками от деления m на соответствующие числа n1, n2, …, nk.

Так как числа n1, n2, …, nk взаимно просты, по китайской теореме об остатках существует единственное решение системы сравнений:
m ≡ d1 (mod n1)
m ≡ d2 (mod n2)
…
m ≡ dk (mod nk)

Поэтому минимальное натуральное число m, удовлетворяющее условиям m%n1 ≠ d1, m%n2 ≠ d2, … m%nk ≠ dk, будет равно r(n-1) + 1, где r - наименьшее целое положительное число, удовлетворяющее этим условиям.

Таким образом, верхняя оценка для минимального натурального числа m будет равна n*(n-1) + 1.