RE: [obm-l] Problemas de Congruência

["Qwert Smith" <lord_qwert@xxxxxxxxxxx>]

Nao sou a melhor pessoa pra fazer esses exercicios, mas como quase ninguem 
se manifestou vamos la.  Quase todos os problemas se resumem em escolher 
numeros menores pra ir simplificando as contas.  O numero de passos e o 
tamanho desses numeros menores e ao gosto do fregues e depende da sua boa 
vontade de fazer contas ou da capacidade da calculadora a sua frente.

>From: Adroaldo Munhoz <amunhoz@gmail.com>
>
>1) Determine o algarismo das unidades de 3^100
A resposta ja foi dada pelo cleber

>2) Determine o resto da divisão de 37^13 por 17
37 = 3 ( mod 17 ) ==> 37^13 (mod 17) = 3^13 (mod 17)
a) 3^13 = 3^5*3^5*3^3
b) 3^5 = 243 = 5 (mod 17)
c) 3^3 = 27 = 10 (mod 17)
3^13 (mod17) = 5*5*10 (mod 17) = 250 (mod 17) = 12 (mod 17)

>3) Mostre que 2^83 – 1 é divisível por 167
2^9 = 512, 167*3 = 501 ==> 2^9 = 11 (mod 167)
2^83=2^81*2^2=(2^9)^9*4
2^83 (mod 167) = 11^9*4 (mod 167)
11^3=1331, 167*8=1336 ==> 11^3 = -5 (mod 167)
11^9*4 ( mod 167) = (-5)^3*4 (mod 167) = -500 (mod 167) = 1 (mod 167)
2^83 -1 (mod 167) = 1 -1 (mod 167) = 0 (mod 167)

>4) A que número entre 0 e 6 é congruente módulo 7 o produto 
>11.18.2322.13.19 ?
11 = 4 mod 7, 18 = 4 mod 7, 13 = -1 mod 7, 19 = -2 mod 7, 2322 = -2 mod 7
4*-2*4*-2*-1 = -1*-1*-1 = -1 = 6 (mod 7)

>5) Fermat conjecturou que todo número da forma Fn = 2^2 + 1 é primo, e 
>provou que isto é verdade para n = 0,1,2,3,4. Porém, a afirmação é falsa 
>para n = 5 já que Euler provou que F_5 é divisível por 641. Mostre isto 
>usando congruências.
A conjectura nao era bem essa.  Era pra ser Fn = 2^(2^n)+1
Para n=5 significa F_5 = 2^32 + 1
E pede pra mostrar que 2^32 + 1 e divisivel por 641 o que e analogo ao 
problema (2)
2^16 = 154 ( mod 641) => 2^32 = (2^16)^2 = 154^2 (mod 641)
154^2 = 23716 = -1 (mod 641) ==> 2^32 +1 = -1 +1 = 0 (mod 641)


>6) Mostre que o quadrado de qualquer inteiro é côngruo a zero ou 1 módulo 4

0 (mod 4) => 0^2 = 0 (mod 4)
1 (mod 4) => 1^2 = 1 (mod 4)
2 (mod 4) => 2^2 = 0 (mod 4)
3 (mod 4) => 3^2 = 1 (mod 4)

>7) Mostre que o quadrado de qualquer inteiro é côngruo a zero , 1 ou 4 (mod 
>8)
Analogo ao exercicio (6)

>8) Se 4 for o maior inteiro que puder ser armazenado em um (micromicro) 
>computador, qual será o resultado armazenado como resultado de 3 + 4 se a 
>soma módulo 5 for usada ?
Nao sei se entendi ... 3+4 = 7 = 2 (mod 5) ... sera isso?


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================