Question

РЕШИТЕЕЕ СРОЧНОО! Какое наименьшее простое число при делении на 3 и на 7 дает остаток 1?

Answer 1

3*7=21
ближайшее простое - 23, но оно больше 21 на 2
3*7*2=42
ближайшее простое 43, которое больше 42 на 1
ответ 43

Answer 2

Для нахождения наименьшего простого числа, которое при делении на 3 и на 7 дает остаток 1, мы можем использовать китайскую теорему об остатках.

Сначала найдем наименьшее число, которое дает остаток 1 при делении на 3. Это число 4, так как 4 = 3*1 + 1.

Затем найдем наименьшее число, которое дает остаток 1 при делении на 7. Это число 1, так как 1 = 7*0 + 1.

Теперь мы можем использовать китайскую теорему об остатках, чтобы найти наименьшее число, которое удовлетворяет обоим условиям. По этой теореме, такое число будет находиться вида x = a (mod m), где a - остаток при делении, а m - модуль (в данном случае 3 и 7).

Для нахождения x, можем воспользоваться следующей формулой: x = a1 * m2 * inv(m2) + a2 * m1 * inv(m1), где a1 = 1 (остаток при делении на 3), m1 = 3 (модуль), a2 = 1 (остаток при делении на 7), m2 = 7 (модуль), inv(m1) - обратное значение m1 по модулю m2, inv(m2) - обратное значение m2 по модулю m1.

Подставим значения и найдем x: x = 1 * 7 * inv(7) + 1 * 3 * inv(3), x = 7 * inv(7) + 3 * inv(3).

Теперь найдем обратные значения: inv(7) = 1 (по модулю 3), inv(3) = 1 (по модулю 7).

Подставляем обратные значения: x = 7 * 1 + 3 * 1, x = 7 + 3, x = 10.

Итак, наименьшее простое число, которое при делении на 3 и на 7 дает остаток 1, равно 10.