Teorema chinês do resto, congruência

Qual o resto na divisão 2^327 por 1463?

Gabarito: 1338

Decomponha 14643

1463 = 7 . 11 . 19

Note que: 327 = 109 . 3

Encontrando o resto de 2^(327) por 7.

2^(327) _= (8 )^(109) _= 1^(109) _= 1 (mod 7)

Pelo teorema de Fermat, se a é um inteiro e p é primo, então:

a^p _= a (mod p)

Então:

2^(11) _= 2 (mod 11)

Como mdc(11, 2) = 1, então.

2^(10) _= 1 (mod 11)

Note que:

329 = 32 . 10 + 9

Então:

2^(327) = 2^(32 . 10) . 2^7 _= 1 . 2^7 _= 2^7  _= 128  _= 7  (mod 11)

Achando o resto de 2^(327) mod 19:

Pelo teorema de Fermat:

2^(18) _= 1 (mod 19)

Note que:

327 = 18 . 18 + 3

Logo:

2^(327) = 2^(18 . 18) . 2^3 _= 1 . 8 _= 8 (mod 19)

Então temos o seguinte sistema de congruência

2^(327) _= 1 (mod 7)
2^(327) _= 7 (mod 11)
2^(327) _= 8 (mod 19)

Agora usaremos o algoritmo que utiliza o teorema chinês dos restos.

Para facilitar fazemos a tabela:

 .....................................A    |.    M.    |.    M'.   |.  M^(- 1) | S
 .......................................... |.            |.            |.                |
2^(327) _= 1 (mod 7).    1.   |.  209.  |.    6.    |   6.           |1254
2^(327) _= 7 (mod 11).  7.   |.  133.  |.    1.    |   1.          | 931
2^(327) _= 8 (mod 19).  8.   |.  77.    |      1.   |   1.          | 616

A é a classe de equivalência de número que queremos achar.

M é o produto dos módulos menos o que está na linha.

M' é a classe de equivalência de M pelo módulo que está na linha.

M^(-1) é a classe inversa de M' pelo módulo que está na linha.

S é o produto de A, M e M^(-1)

Precisamos somar o que está na coluna de S

1254 + 931 + 616 = 2801

Logo:

2^(327) _= 2801 _= 1338 (mod 1463)

2^(327) _= 1338 (mod 1463)

Fantástico!!!
Superaks, por que ao invés de multiplicarmos os restos, temos que montar o sistema?

Eu montei um sistema por causa do seu enunciado "Teorema chinês dos restos . Então eu forcei aparecer um sistema para utilizá-lo. Mas usar esse algoritmo aqui nessa situação eu não usaria, pois você faz bem mais rápido multiplicando as potências de 2.

"Porque ao invés de multiplicarmos os restos devemos fazer um sistema ?"

Você diz, fazer isso:

2^(327) _= 1 * 7 * 8 (mod 1463) ?

Isso mesmo. Eu teria feito isso, mas não bate com o resultado. 
Em relação a eu ter escrito ''teorema chinês do resto'', quando o exercício apareceu estava nesse conteúdo.

Isso é completamente errado. Você não resolve um sistema de congruência multiplicando os restos como eu fiz acima. Um dos meios é usando o teorema chinês dos restos como coloquei ou resolvendo um sistema por vez.

Por exemplo, note que:

2^(327) _= 1 _= 8 (mod 7)
2^(327) _= 8 (mod 19)

Então:

2^(327) _= 8 (mod 7 * 19)

Aí você teria esses dois sistemas

2^(327) _= 8 (mod 133)
2^(327) _= 7 (mod 11)

Outro caminho que você poderia recorrer sem usar o algoritmo que eu usei, será pensando em equações diofantinas.

Sabemos que:

133 | 2^(327) - 8 → 133 | 2^(327) - 8 - 133k

11 | 2^(327) - 7 → 11 | 2^(327) - 7 - 11y

Queremos que:

2^(327) - 8 - 133k = 2^(327) - 7 - 11y

11y - 133k = 1

Achar uma solução para isso é bem rápido.

- 133k _= 1 (mod 11)

10k _= 1 (mod 11)

k _= 10 (mod 11)

Logo:

133 | 2^(327) - 8 - 133 . 10 = 2^(327) - 1338

Então

11 | 2^(327) - 1338

133 . 11 | 2^(327) - 1338

2^(327) _= 1338 (mod 1463)

Muito obrigado, Superaks!!!