S-3.40

(a) Mostre que em geral p divide a^p-a, para todo a in Z e para todo p primo p <= 7.
(b) Verifique que se p não divide a, com p nas condições de (a), então p divide a^p-1-1, para todo a in Z.
(c) Ache o resto da divisão por 7 do número 1^6+2^6+3^6+cdots+15^6.
(d) Mostre que se a e b são primos com 7 , então b^6-a^6 é múltiplo de 7 . Em particular, 23^6-18^6 é múltiplo de 7 .

Passo 1

No enunciado temos: (a) mostrar que, para todo primo p<=7 e todo ainZ, vale
pmid a^p - a;
(b) provar que, se pnmid a, então
pmid a^p-1-1;
(c) calcular o resto de
1^6+2^6+3^6+cdots+15^6
na divisão por 7;
(d) mostrar que, se gcd(a,7)=gcd(b,7)=1, então 7mid b^6 - a^6, em particular para a=18, b=23.
Vamos usar o Teorema do Binômio (coeficientes binom pk são múltiplos de p quando 1<= k<= p-1) e o Pequeno Teorema de Fermat.

Passo 2

Para (a), como p é primo, todo coeficiente binom pk com 1<= k<= p-1 é múltiplo de p. Pelo Teorema do Binômio,
(a+1)^p ;=;sumk=0^pbinom pk,a^k ;=;a^p ;+;binom p1a^p-1+cdots+binom pp-1a ;+;1
Reduzindo módulo p, todos os termos binom pk a^k (com 1<= k<= p-1) desaparecem, ficando
(a+1)^p equiv a^p + 1 pmod p
Uma indução em a mostra então que
a^p equiv a pmod p forall,ainZ,
isto é pmid a^p - a.
Para (b), se pnmid a podemos “cancelar” a na congruência a^pequiv apmod p, obtendo
a^p-1equiv1pmod p,
ou seja pmid a^p-1-1.

Passo 3

Em (c) queremos o resto de
S = sumk=1^15k^6
quando dividido por 7. Pelas conclusões acima, sempre que knotequiv0pmod7 vale k^6equiv1pmod7, e para kequiv0pmod7 vale k^6equiv0pmod7. Entre 1 e 15 há exatamente 2 múltiplos de 7 ( 7,14) e 13 inteiros não múltiplos. Logo
Sequiv 13cdot1 ;+;2cdot0 ;=;13 equiv6pmod7

Passo 4

Em (d), se gcd(a,7)=gcd(b,7)=1 então, pelo item (b),
a^6equiv1pmod7 e b^6equiv1pmod7
Subtraindo,
b^6 - a^6 equiv1 - 1 = 0pmod7,
ou seja 7mid b^6 - a^6. No caso particular a=18, b=23, segue imediatamente que 7mid23^6 -18^6.

Resposta

(a) e (b) seguem do Teorema do Binômio e do Pequeno Teorema de Fermat.
(c) O resto de 1^6+2^6+cdots+15^6 por 7 é boxed6.
(d) Foi mostrado que 7mid b^6 - a^6 sempre que gcd(a,7)=gcd(b,7)=1; em particular 7mid23^6 -18^6.

Exercícios relacionados