Teoria de números congruência

Olá! Para a resolução dos problemas, vamos lançar mão da congruência e de uma consideração. CONGRUÊNCIA. Se a, b e n pertencem a Z e a é congruente a b módulo n, então n divide a – b ou a = b (mod n) => n | (a-b) Teorema de Fermat: Seja a um inteiro positivo e p um primo, então a^p = a (mod p) CONSIDERAÇÃO: 10^10 + 10^102+ + 10^10 100 = 10^10 + 10^102+ 10^10. RESOLUÇÃO. 1 - O resto da divisão de 10^10 + 10^102+ 10^10 por 7. 10 = 3 (mod 7) => *porque 10 – 3 = 7 10^2 = 3^2 (mod 7) *elevamos a igualdade ao quadrado 10^2 = 9 (mod 7) 10^2 = 2 (mod 7) * 9 = 2 (mod 7) *igualdade 1 [10^2]^5 = 2^5 (mod 7) *elevamos a igualdade a quinta potência 10^10 = 32 (mod 7) 10^10 = 4 (mod 7) *32 = 4 (mod 7) * igualdade 2 [10^10]^2 = 4^2 (mod 7) *elevamos a igualdade ao quadrado 10^20 = 16 (mod 7) 10^20 = 2 (mod 7) * 16 = 2 (mod 7) [10^20]^5 = 2^5 (mod 7) *elevamos a igualdade a quinta potência 10^100 = 32 (mod 7) 10^100 = 4 (mod 7) *32 = 4 (mod 7) *igualdade 3 [10^100]*[10^2] = 4*2 (mod 7) * Multiplicamos a igualdade 1 pela 3 10^102 = 8 (mod 7) 10^102 = 1 (mod 7) *porque 8 = 1 (mod 7) * igualdade 4 Devido as igualdades 2 e 4 temos: 10^10 + 10^102 + 10^10 = 4 (mod 7) + 1 (mod 7) + 4 (mod 7) => 10^10 + 10^102 + 10^10 = 2 (mod 7) O resto da divisão de 10^10 + 10^102 + 10^10 por 7 é 2 porque (10^10 + 10^102 + 10^10) – 2 = 7. 2 - Pelo teorema de Fermat Ache o resto da dividão 2^9, 3^8, 5^13 por 7. 2^9 por 7. Seja r o resto. 2^9 – r = 7 => 2^9 = r (mod 7) => *congruência (2^2)*2^7 = r (mod 7) => (2^2)*2 = r (mod 7) => *porque 2^7 = 2 (mod 7) *Fermat 8 = r (mod 7) => 8 – r = 7 *congruência. r = 1 3^8 por 7. Seja r o resto. 3^8 – r = 7 => 3^8 = r (mod 7) => *congruência (3)*3^7 = r (mod 7) => (3)*3 = r (mod 7) => *porque 3^7 = 3 (mod 7) *Fermat 9 = r (mod 7) => 9 – r = 7 *congruência. r = 2 5^13 por 7. Seja r o resto. 5^13 – r = 7 => 5^13 = r (mod 7) => *congruência 5*5^13 = 5*r (mod 7) => *multiplicamos por 5 a igualdade. 5^14 = 5*r (mod 7) => (5^7)*(5^7) = 5*r (mod 7) => (5)*(5) = 5*r (mod 7) => *porque 5^7 = 5 (mod 7) *Fermat 5 = r (mod 7) => *dividimos a igualdade por 5. r = 5 (mod 7) => *propriedade simétrica da congruência r = 5 3 - Pelo teorema de Euler encontre p resto da divisão 3^100 por 37. Devemos encontrar p para 3^100 = p (mod 37) *Igualdade E. 3 = 3 (mod 37) => 3^4 = 3^4 (mod 37) => 3^4 = 81 (mod 37) => 3^4 = 7 (mod 37) => *81 = 7 (mod 37) *igualdade A. 3 = 3 (mod 37) => 3^3 = 3^3 (mod 37) => 3^3 = 27 (mod 37) => *Igualdade B. (3^4)^2 = 7^2 (mod 37) => *Elevamos a igualdade A ao quadrado. 3^8 = 49 (mod 37) => 3^8 = 12 (mod 37) => *Igualdade C. (3^3)*(3^8) = 27*12 (mod 37) => * fizemos Igualdade B vezes a C. 3^11 = 324 (mod 37) => 3^11 = 28 (mod 37) => * 324 = 28 (mod 37) *Igualdade D. (3^11)*(3^100) = 28*p (mod 37) => *Multiplicamos as Igualdades D e E. 3^111 = 28*p (mod 37) => (3^37)^3 = 28*p (mod 37) => (3)^3 = 28*p (mod 37) => *3^37 = 3 (mod 37) *Fermat 27 = 28*p (mod 37) => 28*p = 27 (mod 37) => *propriedade simétrica da cpngruência 28*p = 952 (mod 37) => *27 = 952 (mod 37) 28*p = 952 (mod 37) => *27 = 952 (mod 37) p = 34 (mod 37) => *Dividimos a igualdade por 28. p = 34