Exercícios Resolvidos

1.  Use o pequeno teorema de Fermat para determinar os últimos algarismos dos números e escritos no sistema posicional com base .

Sugestão:

Se temos números e e queremos escrever em notação de sistema posicional com base , no primeiro passo dividimos por , pois o resto obtido é o último (colocado mais a direita) dos algarismos procurados. Portanto, procuramos tal que 0 ≤ r < k e n º r(mod k)

Resolução:

Inicialmente procuramos r ∈ ℕ, r < 7 , tal que 3⁸ º  r(mod 7) .

Do pequeno teorema de Fermat sabemos que 3⁷ º  3(mod 7) .

Portanto 3 ⁸ = 3 ⁷ · 3 º  3 ² (mod 7) º  2 (mod 7)                                .

A resposta obtida é: o último algarismo de no sistema com base é .

Em seguida passamos ao caso de .

O cálculo é seguinte: já que 20 = 7 · 3 – 1 , então

3 ²⁰ = (3 ⁷) ³ · 3^-1 º  3 ³ · 3^-1 (mod 7) º  3 ² (mod 7)  º  2 (mod 7)             .

Isto significa que também aqui o algarismo obtido é .

Um outro caminho:

já que para p∈ e  a < p temos  a ^p º a (mod p), então a ^p-1 º 1 (mod p) .

Daqui temos 3 ⁶ º 1 (mod 7)  e, consequentemente

3 ²⁰ = 3 ⁶ · ^{3 + 2} = (3 ⁶) ³ · 3 ² º  1 ³ .  3 ²(mod 7) º 2 (mod  7).

2. Problema: Determine o resíduo positivo mínimo de a) 5 ¹⁶ (mod 17) b) 5 ⁵⁰⁰ (mod 17)

Sugestão: Use o pequeno teorema de Fermat

Resolução:

a)

a = 5 e p = 17 (primo)

5 ¹⁶ = 1 (mod 17)

b)

Pela alínea a) sabemos que 5¹⁶ = 1 (mod 17)

Como 5 ⁵⁰⁰ = 5 ^{31 × 16 + 4}  = (5 ¹⁶) ³¹ × 5 ⁴ = 5 ⁴ (mod 17) º 13 (mod 17)

Cálculo auxiliar: 500 = 16 × 31 + 4

3. Problema: Dividir um quadrado em dois quadrados. Seja a sua área 16.

Resolução:

 Seja x um quadrado e 16-x² o outro. Temos que transformar 16-x² num quadrado. Método de Fermat: encontrar por tentativas o quadrado sabendo que tem a forma de (ax ± b)² .

      (1)         (2x-4)² =  4x² -16x + 16

      (2)        (2x-4)² =  16-x²

              ^{(1) e (2) Þ}  4x² -16x + 16  =  16-x^{2     Û}

                              ^Û 5x² -16x = 0   ^Û

                        ^{Û  x (5x-16) = 0    Þ}