Question

Доказать, что (10^6+5^7) делится на 23

Answer 1

(10⁶ + 5⁷) = (5 * 2)⁶ + 5⁷ = 5⁶ * 2⁶ + 5⁷ = 5⁶(2⁶ + 5) = 5⁶ * 69 = 23 * 3 * 5⁶
Если один из множителей делится на 23, то и всё произведение делится
на 23.

Answer 2

Для того чтобы доказать, что (10^6+5^7) делится на 23, нужно показать, что остаток от деления этого числа на 23 равен нулю.

Для этого воспользуемся малой теоремой Ферма, которая утверждает, что для любого простого числа p и любого целого числа a, не делящегося на p, верно:

a^(p-1) ≡ 1 (mod p)

Эта теорема позволяет сократить большие степени чисел по модулю простого числа.

Применяя малую теорему Ферма к числу 10 по модулю 23, получаем:

10^22 ≡ 1 (mod 23)

Это значит, что любая степень числа 10, кратная 22, дает остаток 1 при делении на 23.

Теперь заметим, что:

5^7 = 5^6 * 5 = (5^2)^3 * 5 = 25^3 * 5 ≡ 1^3 * 5 ≡ 5 (mod 23)

Здесь мы использовали то, что 25 ≡ 2^2 ≡ -1 (mod 23) в силу китайской теоремы об остатках.

Таким образом,

10^6 + 5^7 ≡ 10^6 + 5 ≡ 10^6 * 10^16 + 5 * 10^16 + 5 ≡ (10^22)^16 * 10^4 + 5 * 10^16 + 5 ≡ 1^16 * 10^4 + 5 * 10^16 + 5 ≡ 5 * (10^16 + 1) (mod 23)

Мы получили, что (10^6+5^7) кратно 5, а также кратно выражению 10^16 + 1. Поскольку 10^16 ≡ 1 (mod 23) по малой теореме Ферма, то 10^16 + 1 ≡ 2 (mod 23). Значит, (10^6+5^7) кратно 2 и 5, и, следовательно, кратно 10. Но 23 и 10 взаимно просты, поэтому (10^6+5^7) должно быть кратно 23. Таким образом, мы доказали, что (10^6+5^7) делится на 23.