Obra: Apostila OBMEP 7
Matéria: Matemática
Nível: fundamental
SUMZFI GCSGC SVZFC LZLSJ EZQSL HIFUI JDZQS LTSRF
SGCSJ UOZSZ OJTZL ZOEEO LHMSE ESDSL IECLU ILHCD
ZTIFE SZMOJ QCZSU IJPSU OTZZL ZOIFH ZFDST IHFIU SEEIH
ITSES FZCDI LZDOA ZTIIG CSDIF JZOJB OZBSO EDITI EIEUI
TOQIE GCSSJ BIMBS LECVE DODCO UZITS MSDFZ EUILI
IGCSS EDZLIE CDOMO AZJTI HZFZU ITORO UZFSE DZLSJ
EZQSL JZBSF TZTSZ MQCJE TIEHF OLSOF IEUIL HCDZT

“principal”
2010/4/20
page 4
Estilo OBMEP
 
IFSER IFZLU FOZTIE HFSUO EZLSJ DSHZF ZZNCT ZFZGC
SVFZFI EUITO QIEES UFSDI ECEZTI EHSMIE ZMSLZSE
TCFZJDS ZESQC JTZQC SFFZL CJTOZM SJDFS SEDSE SEDZB
ZIUIM IEEICL UILHC DZTIF UIEJD FCOTI JZOJQ MZDSF
FZHIF CLZSG COHSM OTSFZ TZHIF ZMZJD CFOJQ CLTIE
RCJTZ TIFSE TZUILH CDZUZI UOSJDO ROUZ
Exercício 1. Será que você notou que o parágrafo acima foi codifi-
cado? Use o método de contagem de frequência para quebrar o có digo
cluir que o número dado é primo. Por exemplo, se queremos fatorar
91, devemos verificar se é divisível
por 2? não, pois é ímpar;
por 3? como 9 + 1 = 10 não é divisível por 3 então 91 também
não é;
por 4? podemos pular 4 já que 91 é ímpar;
por 5? não, já que não acaba em 5 nem em 0;
por 6? outro par que podemos pular;
por 7? dividindo 91 por 7 achamos resto zero e quociente 13;
logo, 7 e 13 são fatores de 91. Note que houve bastante redundância
Estilo OBMEP
▲ SEC. 1.2: FATORANDO INTEIROS 33
12 103 2 . . . não divisível
12 103 3 . . . não divisível
12 103 5 . . . não divisível
12 103 7 . . . divisível
1 729 7 . . . divisível
247 9 . . . não divisível
247 11 . . . não divisível
247 13 . . . divisível
19 13 . . . não divisível
19 15 . . . não divisível
19 17 . . . não divisível
19 19 . . . divisível
Estilo OBMEP
▲ SEC. 2.3: CRITÉRIOS DE DIVISIBILIDADE 65
a adição e a multiplicação à congruência, concluímos que
an10n+an− 110n− 1+· · ·+a110+a0 ≡ an+an− 1+· · ·+a1+a0 (mod 3) .
Logo, pela transitividade,
a ≡ an + an− 1 + · · · + a1 + a0 (mod 3) ,
que é exatamente o que precisamos para podermos concluir o critér io
Estilo OBMEP
▲ SEC. 3.4: O TEOREMA E UM EXEMPLO 97
• se r for o resto da divisão de n por m então r = 0 ou r ̸= 0;
• se r ̸= 0 então mostramos que r pertenceria a V (a, n);
• como o resto é sempre menor que o divisor, teríamos r < m ;
• mas isto não é possível pela escolha que fizemos para m;
• portanto, r = 0 e m divide n.
e o resto da divisão de 21398 765
por 31 é 8. Mais difícil foi, mas não
“muiiiiito mais difícil!”
Exercício 43. Calcule o resto da divisão por 31 das potências 21445 231
215498 766 543 335 231
e 6439 876
5.1.2 Ordem de um Inteiro Modular
Os cálculos com potências feitos acima só foram tão fáceis de exe-
Precisamos experimentar um pouco mais, antes de ensaiar uma con-
clusão. Revendo os exemplos do início desta seção constatamos que 7
e 31 são primos, mas o que acontece se escolhermos um módulo que
não seja primo? Por exemplo, será que existe uma potência de 2 que
dá 1 módulo 6? Tentando:
21 ≡ 2 (mod 6) ,
22 ≡ 4 (mod 6) ,
23 ≡ 8 ≡ 2 (mod 6) ,
24 ≡ 16 ≡ 4 (mod 6) ,
e já deu para ver que os valores das potências de 2 módulo 6 vão se
Voltando aos nossos experimentos, porque parar em 2? Por que
não tentar também 3? Pois bem, aqui estão as potências de 3 módulo
31 ≡ 3 (mod 6) ,
32 ≡ 9 ≡ 3 (mod 6) ,
33 ≡ 27 ≡ 3 (mod 6) ,
34 ≡ 81 ≡ 3 (mod 6) .
Não é que 3 foi ainda pior que 2! Todas as potências positivas de 3
são congruentes a 3. Mas, não desanimemos, tentemos as potências
de 4,
41 ≡ 4 (mod 6) ,
42 ≡ 16 ≡ 4 (mod 6) ,
cermos a ordem de 2. Usando esta última congruência,
364 ≡ (33)21 · 3 ≡ (− 22)21 · 3 ≡ − (2)42 · 3 (mod 31) .
Como 25 ≡ 1 (mod 31) e 42 = 8 · 5 + 2, temos que
242 ≡ (25)8 · 22 ≡ 4 (mod 31) .
Assim,
364 ≡ − (2)42 · 3 ≡ − 4 · 3 ≡ − 12 (mod 31) .
Como − 12 ≡ 19 (mod 31) , o resto da divisão de 364 por 31 é 19.

“principal”
2010/4/20
page 134
particular, qualquer um destes elementos admite uma ordem módulo
p. Note, contudo, que não podemos afirmar que, como
bp− 1 ≡ 1 (mod p) se b ̸≡ 0 (mod p),
então b tem ordem p − 1 módulo p. Para começar, 1 tem ordem 1
módulo p qualquer que seja o p que você escolher. Além disso, como
(p − 1) ≡ − 1 (mod p),
Desafio 5. Seja p um primo positivo e b um inteiro que não é divisível
por p. Digamos que k é a ordem de b módulo p.
(a) Explique porque k ≤ p − 1.
(b) Seja r o resto da divisão de p − 1 por k. Mostre que, como
ap− 1 ≡ ak ≡ 1 (mod p),
então ar ≡ 1 (mod p).
(c) Lembrando que 0 ≤ r ≤ k − 1, mostre que r = 0.
(d) Conclua que a ordem de b é um divisor de p − 1.
de Fermat quando o módulo é primo . Como
1 033 = 32 , 14 . . .
só precisamos mostrar que 1 033 não é divisível pelos primos menores
que 32 para ter certeza que é primo. Estes primos são,
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
e é fácil verificar que nenhum deles divide 1 033. Agora que temos

“principal”
2010/4/20
page 141
Reunindo todos os blocos, descobrimos que a mensagem codificada é
34 − 129 − 228 − 37 − 207 − 105 − 44 − 386 − 125.
Exercício 56. Use a chave pública que você construiu no exercício
55 para codificar seu nome. Escreva a chave e a mensagem em um
papel. Os papéis deverão ser reunidos, embaralhados e sorte ados entre
aplica a p# − 1, como você é chamado a mostrar no próximo exercício.
Exercício 61. Seja p um primo.
(a) Mostre que p# e p# − 1 não têm fatores comuns.
(b) Use (a) para mostrar que existem infinitos números primos .
(c) Determine o menor primo ímpar p para o qual p# − 1 é com-
posto.
São conhecidos apenas 18 primos da forma p# − 1, o maior deles
é 15 877# − 1 que tem 6 845 algarismos.

“principal”
2010/4/20
page 172
Portanto, o teorema nos diz que se p é primo então uma certa con-
gruência tem que ser verdadeira . Considere, então, o seguinte número
de 101 algarismos,
R(101) = 111111111111111111111111111111111111111111111 1111
1111111111111111111111111111111111111111111111111111.

“principal”
2010/4/20
page 188
do livro [2].
Exercício 63. O objetivo deste exercício é comprovar o resultado de
Euler, segundo o qual 641 divide F (5).
(a) Mostre que 641 = 2 7 · 5 + 1 e que 641 = 2 4 + 54.
(b) Use (a) para mostrar que F (5) · 5 ≡ 0 (mod 641) .
(c) Explique porque (b) implica que F (5) ≡ 0 (mod 641) .
Os números da família R(n) têm uma história mais recente: foram
Estilo OBMEP
▲ SEC. 7.3: UM TESTE DE COMPOSIÇÃO 199
(b) Mostre que se k é um fator de n então R(k) divide R(n).
(c) Determine todos os fatores primos de R(6).
(d) Mostre que se R(n) for primo então n tem que ser primo.
(e) Mostre que R(7) é composto usando o teste desta seção.
Você vai precisar de uma calculadora para fazer os itens (c) e (d)
62. Os primos são:
5 11 17 23 29 41 47 53 59 71
83 89 101 107 113 131 137 149 167 173
179 191 197 227 233 239 251 257 263 269
281 293 311 317 347 353 359 383 389 401
419 431 443 449 461 467 479 491
63. (b) Como 32 = 4 · 7 + 4, temos que
F (5) · 54 ≡ (27 · 5)4 · 24 + 54 ≡ 0 (mod 641) .
(c) Como 5 é inversível módulo 641 podemos concluir de (b)
dividem R(6) por (b). Mas,
R(6)
3 · 11 · 37 = 91 = 7 · 13.
Logo,
R(6) = 3 · 7 · 11 · 13 · 37.
(d) Consequência imediata de (b).
(e) Como R(7) − 1 = 10 · R(6) podemos usar a fatoração de
R(6) obtida acima para facilitar o cálculo do resíduo de 2
módulo R(7), que dá 553 891.

“principal”
2010/4/20
page 216