a) Encontre um inteiro x tal que x ≡ 3 (mod 10), x ≡ 11 (mod 13) e x ≡ 15 (mod 17)(Regiomantanus, século XVI).

b) Encontre um inteiro x tal que x ≡ 3 (mod 11), x ≡ 5 (mod 19) e x ≡ 10 (mod 29)(Euler, século XVIII).

Passo 1

Fala minha galera, bora extrair o máximo dos nossos pensamentos com esse exercício de algelin!

Vamos aplicar o teorema Chinês do resto, nosso querido TCR, isto é, temos que descobrir x 0 - = a 1 ⋅ n 1 ⋅ x 1 + a 2 ⋅ n 2 ⋅ x 2 + a 3 ⋅ n 3 ⋅ x 3 .

  1.   x ≡ 3   ( m o d   10 ) ,   x ≡ 11 ( m o d   13 )   e   x ≡ 15   ( m o d   17 ) . Vamos separar nas incógnitas de acordo com o TCR.
  2. a 1 = 3 , a 2 = 11 ,   a 3 = 15 ;

    n 1 = 10 , n 2 = 13 ,   n 3 = 17 ;

    n = 10 ⋅ 13 ⋅ 17 = 2210 ;

    N 1 = 13 ⋅ 17 = 221 ,   N 2 = 10 ⋅ 17 = 170 ,   N 3 = 10 ⋅ 13 = 130 .

    As congruências N 1 x 1 ≡ 1   m o d   10 ,   N 2 x 2 ≡ 1   m o d   13 ,   N 3 x 3 ≡ ( m o d   17 ) , são:

    221 x 1 ≡ 1   ( m o d   10 ) , 221 ÷ 10 → 22 10 + 1 então podemos reescrever como 1 x 1 ≡ 1   ( m o d   10 ) ;

    170 x 2 ≡ 1   m o d   13 , 170 ÷ 13 → 13 13 + 1 então podemos reescrever como 1 x 2 ≡ 1   ( m o d   13 ) ;

    130 x 3 ≡ 1   ( m o d   17 ) , 130 ÷ 17 → 7 17 + 11 então podemos reescrever como 11 x 3 ≡ 1   ( m o d   17 ) ,

    11 ⋅ k + 17 ⋅ k 0 = 1 → u m a   s o l u ç ã o   é   k , k 0 = ( - 3 ,   2 )

    A solução é x 3 ≡ - 3   ( m o d   17 ) .

    Agora sim podemos solucionar o problema pois temos todas as variáveis da expressão!

    x 0 - = 3 ⋅ 221 ⋅ 1 + 11 ⋅ 170 ⋅ 1 + 15 ⋅ 130 ⋅ - 3 = - 3317

    A solução geral do problema então é

    x = x 0 - + n t   c o m   t ∈ Z

    x = - 3317 + 2210 t

    Podemos reescrever para deixar positivo da seguinte forma, como x = 1103 + 2210 t , pois 2210 ⋅ 2 - 3317 = 1103 .

    Passo 2

  3. x ≡ 3   m o d   11 ,   x ≡ 5 ( m o d   19 )   e   x ≡ 10   ( m o d   29 ) . Vamos separar nas incógnitas de acordo com o TCR.

a 1 = 3 , a 2 = 5 ,   a 3 = 10 ;

n 1 = 11 , n 2 = 19 ,   n 3 = 29 ;

n = 11 ⋅ 19 ⋅ 29 = 6061 ;

N 1 = 19 ⋅ 29 = 551 ,   N 2 = 11 ⋅ 29 = 319 ,   N 3 = 11 ⋅ 19 = 209 .

As congruências N 1 x 1 ≡ 1   m o d   11 ,   N 2 x 2 ≡ 1   m o d   19 ,   N 3 x 3 ≡ ( m o d   29 ) , são:

551 x 1 ≡ 1   ( m o d   11 ) , 551 ÷ 11 → 50 11 + 1 então podemos reescrever como 1 x 1 ≡ 1   ( m o d   11 ) ;

319 x 2 ≡ 1   m o d   19 , 319 ÷ 19 → 16 11 + 15 então podemos reescrever como 15 x 2 ≡ 1   ( m o d   19 ) ,

15 ⋅ k ' + 19 ⋅ k 0 ' = 1 → u m a   s o l u ç ã o   é   k ' , k 0 ' = ( - 5 ,   4 )

A solução é x 2 ≡ - 5   ( m o d   19 ) ;

209 x 3 ≡ 1   ( m o d   29 ) , 209 ÷ 29 → 7 29 + 6 então podemos reescrever como 6 x 3 ≡ 1   ( m o d   29 ) ,

6 ⋅ k + 29 ⋅ k 0 = 1 → u m a   s o l u ç ã o   é   k , k 0 = ( 5 ,   - 1 )

A solução é x 3 ≡ 5   ( m o d   29 ) .

Agora sim podemos solucionar o problema pois temos todas as variáveis da expressão!

x 0 - = 3 ⋅ 551 ⋅ 1 + 5 ⋅ 319 ⋅ - 5 + 10 ⋅ 209 ⋅ 5 = 4128

A solução geral do problema então é

x = x 0 - + n t   c o m   t ∈ Z

x = 4128 + 6061 t  

Resposta

  1. 1103
  2. 4128