докажите что 300 в степени 3000 минус 1 делится на 1001
Чтобы показать, что \( 300^{3000} - 1 \) делится на \( 1001 \), начнем с разложения числа \( 1001 \) на простые множители. Мы можем записать:
\[ 1001 = 7 \times 11 \times 13 \]
Теперь нам нужно доказать, что \( 300^{3000} - 1 \) делится на каждое из этих простых множителей: 7, 11 и 13.
Шаг 1: Делимость на 7
Сначала найдем \( 300 \mod 7 \): \[ 300 \div 7 = 42 \quad \text{(целое число)} \] \[ 300 - 7 \times 42 = 6 \quad \Rightarrow \quad 300 \equiv 6 \mod 7 \]
Теперь вычислим \( 300^{3000} \mod 7 \): \[ 300^{3000} \equiv 6^{3000} \mod 7 \]
Согласно малой теореме Ферма, если \( a \) не делится на \( p \), то \( a^{p-1} \equiv 1 \mod p \). В данном случае \( p = 7 \): \[ 6^{6} \equiv 1 \mod 7 \] Поскольку \( 3000 \) делится на \( 6 \) (поскольку \( 3000 = 6 \times 500 \)), мы получаем: \[ 6^{3000} \equiv (6^{6})^{500} \equiv 1^{500} \equiv 1 \mod 7 \] Таким образом: \[ 300^{3000} - 1 \equiv 1 - 1 \equiv 0 \mod 7 \]
Шаг 2: Делимость на 11
Теперь проверим \( 300 \mod 11 \): \[ 300 \div 11 = 27 \quad \text{(целое число)} \] \[ 300 - 11 \times 27 = 3 \quad \Rightarrow \quad 300 \equiv 3 \mod 11 \]
Вычисляем \( 300^{3000} \mod 11 \): \[ 300^{3000} \equiv 3^{3000} \mod 11 \] По малой теореме Ферма для \( p = 11 \): \[ 3^{10} \equiv 1 \mod 11 \] Поскольку \( 3000 \) делится на \( 10 \): \[ 3^{3000} \equiv (3^{10})^{300} \equiv 1^{300} \equiv 1 \mod 11 \] Значит: \[ 300^{3000} - 1 \equiv 0 \mod 11 \]
Шаг 3: Делимость на 13
Теперь проверим \( 300 \mod 13 \): \[ 300 \div 13 = 23 \quad \text{(целое число)} \] \[ 300 - 13 \times 23 = 1 \quad \Rightarrow \quad 300 \equiv 1 \mod 13 \]
Следовательно, \[ 300^{3000} \equiv 1^{3000} \equiv 1 \mod 13 \] Это дает нам: \[ 300^{3000} - 1 \equiv 0 \mod 13 \]
Заключение
Мы доказали, что \( 300^{3000} - 1 \) делится на \( 7 \), \( 11 \) и \( 13 \). Следовательно, по теореме о делимости произведения простых чисел, можно утверждать, что: \[ 300^{3000} - 1 \equiv 0 \mod 1001 \]
Это означает, что \( 300^{3000} - 1 \) делится на \( 1001 \).
