Prove que 300^{3000} - 1 é divisível por 1001.

Passo 1

O enunciado pede para mostrar que
1001 \mid 300^{3000} - 1.
Aqui usamos teoria de divisibilidade e aritmética modular, mais precisamente o Teorema de Fermat e o Princípio do Resto Chinês.

Passo 2

Note que
1001 = 7 \times 11 \times 13.
Para concluir que 1001 divide 300^{3000}-1, basta provar que cada um de 7, 11 e 13 divide 300^{3000}-1, pois são primos distintos.

Passo 3

Verificação módulo 7.
Primeiro, 300\mod7 = 300 - 7\cdot42 = 6. Logo
300^{3000} \equiv 6^{3000} \pmod{7}.
Como 7 é primo, pelo Teorema de Fermat 6^6 \equiv 1\pmod{7}. Além disso, 3000 é par, então 6^{3000} = (6^6)^{500} \equiv 1^{500} = 1\pmod{7}.
Logo
6^{3000} - 1 \equiv 0\pmod{7},
ou seja, 7\mid 300^{3000}-1.

Passo 4

Verificação módulo 11.
Calculamos 300\mod11 = 300 - 11\cdot27 = 3. Assim
300^{3000} \equiv 3^{3000} \pmod{11}.
Como 11 é primo, pelo Teorema de Fermat 3^{10}\equiv1\pmod{11}. E 3000 = 10\cdot300, então
3^{3000} = (3^{10})^{300} \equiv 1^{300} = 1\pmod{11}.
Logo
3^{3000} - 1 \equiv 0\pmod{11},
ou seja, 11\mid 300^{3000}-1.

Passo 5

Verificação módulo 13.
Temos 300\mod13 = 300 - 13\cdot23 = 1. Portanto
300^{3000} \equiv 1^{3000} = 1\pmod{13}.
Logo
1^{3000} - 1 = 0\pmod{13},
ou seja, 13\mid 300^{3000}-1.

Passo 6

Como mostramos que
7 \mid 300^{3000}-1,\quad 11 \mid 300^{3000}-1,\quad 13 \mid 300^{3000}-1
e 7, 11, 13 são primos distintos, pelo Princípio do Resto Chinês concluímos que
1001 = 7\cdot11\cdot13 \mid 300^{3000}-1.

Resposta

Portanto, 300^{3000}-1 é divisível por 1001.

Exercícios relacionados