Давайте рассмотрим выражение ( 2^{18} - 5^{6} ) и проверим, делится ли оно на 13. Мы можем использовать теорему Ферма, которая утверждает, что если ( p ) — простое число, то для любого целого числа ( a ) выполняется следующее:
[
a^{p-1} \equiv 1 \mod p
]
Для числа 13, ( p = 13 ), и ( p-1 = 12 ). Мы можем рассмотреть ( 2^{18} ) и ( 5^{6} ) по модулю 13.
Сначала найдём ( 2^{18} \mod 13 ):
- Вычислим ( 2^{12} \mod 13 ) по теореме Ферма:
[
2^{12} \equiv 1 \mod 13
]
- Теперь мы можем записать ( 2^{18} ) как:
[
2^{18} = 2^{12} \cdot 2^6 \equiv 1 \cdot 2^6 \mod 13
]
- Теперь вычислим ( 2^6 \mod 13 ):
[
2^6 = 64
]
[
64 \mod 13 = 12
]
Таким образом, ( 2^{18} \equiv 12 \mod 13 ).
Теперь найдём ( 5^{6} \mod 13 ):
- Сначала вычислим ( 5^{12} \mod 13 ):
[
5^{12} \equiv 1 \mod 13
]
- Теперь вычислим ( 5^{6} \mod 13 ):
[
5^6 = 15625
]
Вычислим ( 5^6 \mod 13 ) (можно использовать степенной метод):
- ( 5^1 \equiv 5 )
- ( 5^2 \equiv 25 \mod 13 = 12 )
- ( 5^3 \equiv 5 \cdot 12 = 60 \mod 13 = 8 )
- ( 5^4 \equiv 5 \cdot 8 = 40 \mod 13 = 1 )
- ( 5^5 \equiv 5 \cdot 1 = 5 )
- ( 5^6 \equiv 5 \cdot 5 = 25 \mod 13 = 12 )
Таким образом, ( 5^6 \equiv 12 \mod 13 ).
Теперь мы можем найти ( 2^{18} - 5^6 \mod 13 ):
[
2^{18} - 5^6 \equiv 12 - 12 \equiv 0 \mod 13
]
Это означает, что ( 2^{18} - 5^6 ) действительно делится на 13. Таким образом, мы доказали, что ( 2^{18} - 5^{6} \equiv 0 \mod 13 ).
