Question

Какой остаток имеет число 222^555 + 555^222 при делении на 7?

Answer 1

1) Сначала найдем остатки оснований при делении на 7.
А) 222=210+12=7*30+7+5 - остаток 5.
Б) 555=490+63+2=7*70+7*9+2 - остаток 2.
2) Теперь возводим эти остатки в степень.
А) 222^555=5^555=(5^5)^111=3125^111=(2800+280+42+3)^111
Оно имеет такой же остаток при делении на 7, как 3^111.
3^111=(3^3)^37=27^37=(21+6)^37 =6^37=6^2*6^35=36*(6^5)^7=
=(35+1)(36*216)^7=1*(35+1)^7*(210+6^7)=1*1^7*6^7=6^7=
=36^3*6=(35+1)^3*6=1^3*6=6
Остаток 222^555 от деления на 7 равен 6.
Б) 555^222=2^222=(2^6)^37=64^37=(63+1)^37=1^37=1.
Остаток 555^222 от деления на 7 равен 1.
3) Складываем эти остатки.
6+1=7
Значит, остаток 222^555+555^222 от деления на 7 равен 7, то есть 0.
Это число делится на 7 нацело.

Answer 2

Давайте найдем остаток от деления числа $222^{555} + 555^{222}$ на 7. Для этого воспользуемся малой теоремой Ферма.

Малая теорема Ферма утверждает, что если $p$ — простое число, то для любого целого числа $a$, не делящегося на $p$, справедливо следующее:

$a^{p-1} \equiv 1 \pmod{p}$

Заметим, что $7$ — простое число. Таким образом, $a^6 \equiv 1 \pmod{7}$ для любого $a$, не делящегося на 7.

Подставим $a = 222$ и $a = 555$ в эту формулу:

$222^6 \equiv 1 \pmod{7}$ $555^6 \equiv 1 \pmod{7}$

Теперь вернемся к нашему изначальному выражению:

$222^{555} + 555^{222}$

Поскольку $222 = 7 \cdot 31$ и $555 = 7 \cdot 79$, то можно выделить 7 в обоих членах:

$7 \cdot (31^{555} + 79^{222})$

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

$31^6 \equiv 1 \pmod{7}$ $79^6 \equiv 1 \pmod{7}$

Исходное выражение преобразуется к следующему:

7 \cdot (31^{555} + 79^{222}) \equiv 7 \cdot (31^{6 \cdot 92 + 3} + 79^{6 \cdot 37]) \pmod{7}

$7 \cdot (31^3 + 79^6) \equiv 7 \cdot (31^3 + 1) \pmod{7}$

Теперь подсчитаем значения:

$31^3 \equiv 1 \pmod{7}$

И, следовательно,

$7 \cdot (31^3 + 1) \equiv 7 \cdot (1 + 1) \equiv 14 \equiv 0 \pmod{7}$

Таким образом, остаток от деления числа $222^{555} + 555^{222}$ на 7 равен 0.