Mostre que se a e n são inteiros positivos pares, então nenhuma potência de a é congruente a 1 módulo n.
Calcule o resto da divisão de 3^98745 por 43 procedendo da seguinte maneira:
(a) Calcule a ordem de 6 módulo 43;
(b) Determine uma potência de 3 que seja congruente a -6 módulo 43;
(c) Use (a) e (b) para calcular o resto desejado.

Passo 1

O exercício tem duas partes. Primeiro, precisamos mostrar que, se a e n são inteiros positivos pares, então nenhuma potência de a pode ser congruente a 1 módulo n. Em seguida, devemos calcular o resto da divisão de 3^98745 por 43 usando três subpassos:
  • (a) encontrar a ordem de 6 módulo 43;
  • (b) achar um expoente de 3 que dê -6 módulo 43;
  • (c) combinar (a) e (b) para obter o resto de 3^98745mod 43.

Passo 2

Mostramos que, se a e n são pares, então gcd(a,n)>=2. Como gcd(a,n) divide todo a^k, temos
gcd(a^k,n);=;l(gcd(a,n)r)^k;>=2^k;>=2
Logo gcd(a^k,n)neq1, o que impede a^kequiv1pmod n. Assim nenhuma potência de a pode ser congruente a 1 módulo n.

Passo 3

(a) Vamos achar a ordem de 6 em Z/43. Queremos o menor d>0 tal que
6^dequiv1pmod43
Calculando:
6^1=6, 6^2=36, 6^3=36cdot6=216equiv216-5cdot43=1pmod43
Logo a ordem de 6 é 3.

Passo 4

(b) Procuramos k tal que
3^kequiv -6pmod43(!-6equiv37bmod43)
Calculando potências de 3:
3^1=3,;3^2=9,;3^3=27,;3^4=81equiv38,;3^5=38cdot3equiv28,;3^6equiv41,;3^7equiv41cdot3equiv123-2cdot43=37
Portanto 3^7equiv37equiv-6pmod43.

Passo 5

(c) Escrevemos
98745 = 7cdot14106 + 3,
de modo que
3^98745 = l(3^7r)^14106cdot3^3 equiv (-6)^14106cdot27pmod43
Como da parte (a) temos 6^3equiv1, segue
(-6)^3 = -l(6^3r)equiv -1pmod43,
e então
(-6)^14106 = l((-6)^3r)^4702 equiv (-1)^4702=1
Logo
3^98745equiv1cdot27=27pmod43

Resposta

Para a,n pares nenhuma potência de a vale 1pmod n.
O resto de 3^98745 na divisão por 43 é 27.

Exercícios relacionados