Наименьшее натуральное число

Пусть искомое число — x. По условию задачи:

x ≡ 1 (mod 7) — x при делении на 7 даёт остаток 1.
x ≡ 3 (mod 9) — x при делении на 9 даёт остаток 3.
Из первого уравнения следует, что x = 7k + 1, где k — целое неотрицательное число.

Подставим это во второе уравнение:

7k + 1 ≡ 3 (mod 9)

7k ≡ 2 (mod 9)

Нам нужно найти такое k, чтобы 7k при делении на 9 давало остаток 2. Можно перебирать значения k:

k = 0: 7 * 0 = 0 ≡ 0 (mod 9)
k = 1: 7 * 1 = 7 ≡ 7 (mod 9)
k = 2: 7 * 2 = 14 ≡ 5 (mod 9)
k = 3: 7 * 3 = 21 ≡ 3 (mod 9)
k = 4: 7 * 4 = 28 ≡ 1 (mod 9)
k = 5: 7 * 5 = 35 ≡ 8 (mod 9)
k = 6: 7 * 6 = 42 ≡ 6 (mod 9)
k = 7: 7 * 7 = 49 ≡ 4 (mod 9)
k = 8: 7 * 8 = 56 ≡ 2 (mod 9)
Значит, k = 8.

Подставим k = 8 в x = 7k + 1:

x = 7 * 8 + 1 = 57

Проверим:

57 / 7 = 8 с остатком 1
57 / 9 = 6 с остатком 3
Условиям задачи удовлетворяет число 57.

Ответ: 57