congruenciaeaneizn

Congruencia e aneis znRodrigo Carlos Silva de Lima

[email protected]

1

Sumario1 Congruencia e aneis zn .

3

1.1

Congruencias modulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

Propriedades basicas de congruencia

6

1.3

Pequeno teorema de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4

Aneis zn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.4.1

. . . . . . . . . . . . . . . . . . . . .

Teorema de Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.5

Aplicacoes de congruencias . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.6

Congruencia e divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2

Captulo 1Congruencia e aneis zn.Esse texto ainda nao se encontra na sua versao nal, sendo, por enquanto, constitudo apenas de anotacoes informais. Sugestoes para melhoria do texto, correcoes daparte matematica ou gramatical eu agradeceria que fossem enviadas para meu [email protected].

1.1m

Congruencias modulo n

Denicao

1. Sejam n 2, a, b Z, dizemos que a e congruente a b modulo n

se n|(a b) e denotamos por a b mod n. Caso a nao seja congruente `a b

mod n

escrevemos a b mod n.Se zermos n = 1 entao para quaisquer a, b inteiros valeriaa b mod 1pois 1|a b, por isso a restricao de tomar n > 1.

b Propriedade 1. A congruencia e uma relacao de equivalencia em Z. Demonstracao. A congruencia modulo n e reexiva, a a mod n, pois n|(a a) = 0. A congruencia modulo n e simetrica, se a b mod n entao b a mod n, pois

se a b mod n, temos n|(a b) implicando n|(b a) logo b a mod n.3

ZN .CAPITULO 1. CONGRUENCIAE ANEIS

4

A congruencia modulo n e transitiva, se a b mod n e b c mod n entao

a c mod n. Se a b mod n temos n|(a b) e com b c mod n segue n|(b c)de onde segue que n|(a b + b c = a c) logo n|(a c) implicando a c mod n.

b Propriedade 2. a b

mod n a e b possuem o mesmo resto na divisao euclidiana

por n. Demonstracao. . Supondo a b mod n , tem-se n|a b. Podemos escreverque a = qn + r e b = q n + r , suponha por absurdo que r = r , da um deles e maior,supondo sem perda de generalidade que r > r tem-se 0 < r r < na b = q(n n ) + r r r r = q(n n ) + (b a)entao n|(r r) o que e absurdo . . Se a e b possuem o mesmo resto entao a = qn+r e b = q n+r, logo ab = (qq )nde onde segue que n|a b da a b mod n.Classe residual modulo nVimos que a congruencia modulo n e uma relacao de equivalencia em Z, vamos veragora qual a classe de um inteiro a na congruencia modulo na = {x Z |x a mod n} = {x Z | n|(x a)}logo e o conjunto dos elementos x de Z tais que x e a deixam o mesmo resto na divisaopor n.

b Propriedade 3. Seja n 2. Para cada a Z existe um unico r Z com 0 r n1tal que a = r, logo com a relacao de equivalencia modulo n temos n classes residuaisdistintas k com k [0, n 1]NZ=

n1

k.

k=0

Demonstracao. Dado a Z, pela divisao euclidiana por n temos um unico r Zcom 0 r n 1 e q Z tal quea = qn + r, a r = qn, n|a r, a r mod n, a = r


5

logo temos a existencia, vamos mostrar agora a unicidade, sendo r e s inteiros tais quer = s ambos no intervalo [0, n 1]N o maximo da diferenca possvel entre r e s e n 1 (ses = 0 e r = n1) e o mnimo e (n+1) (se r = 0 e s = n1) logo n1 rs n1 ecomo temos que r = s temos que n|(r s) porem no intervalo de valores que r s assumeapenas 0 e divisvel por n logo r s = 0, r = s.

$ Corolario 1. Se r e o resto da divisao euclidiana de a por n entao a r mod n , er e o menor valor natural que satisfaz essa propriedade.

m Denicao

2 (Conjunto das classes residuais modulo n). O conjunto quociente de Z

pela congruencia modulo n e representado por Zn e e chamado de conjunto das classesresiduais modulo nZn = {k, k In1 }.

m Denicao

3 (Sistema completo de resduos modulo m). Um conjunto A Z e dito

ser um sistema completo de resduos modulo m, quando o resto dos seus elementos nadivisao por n sao os numeros [0, n 1]N e |A| = n.

b Propriedade 4. Dados n numeros inteiros consecutivos existe apenas um entre elesque e divisvel por n . Demonstracao.UnicidadeDados n numeros consecutivos {y + 1, ..., y + n} a distancia maxima entre eles e n 1que acontece quando tomamos os numeros extremos y + n e y + 1y + n y 1 = n 1.Suponha por absurdo que existem 2 dois numeros y1 e y2 nesse conjunto que sejammultiplos de n com y2 > y1 , existe p natural tal que y2 = y1 + p, onde 0 < p < n, pelofato de ambos serem multiplos de n, existem t1 , t2 Z tais quey2 = n.t2y1 = n.t1


6

da n.t2 = nt1 + p n(t2 t1 ) = p portanto n|p o que e absurdo pois nao existenumero entre 0 e n que seja multiplo de n.Existencia.Temos y + 1 = nq + r onde 0 r < n, portanto existe p N tal que p < n e r + p = ne da y + 1 + p = nq + r + p = nq + n = n(q + 1) < y + 1 + n,y+1y+1+py+no numero y + 1 + p pertence ao conjunto {y + 1, ..., y + n} e e divisvel por n.

1.2

Propriedades basicas de congruencia

b Propriedade 5 (Soma). Se a b

mod n e c d mod n entao a + c b + d mod n.

Demonstracao. ab = qn, cd = q .n logo ab+cd = (a+c)(b+d) = (q+q )nlogo a + c b + d mod n.

b Propriedade 6 (Produto por constante).

Se a b mod n entao a.c b.c mod n

onde c Z. Demonstracao. Vale a b = q.n da ca cb = cqn implicando a.c b.c mod n.

$ Corolario 2. Se a b mod n e c d mod n entao t a + tc t b + td mod n ondet, t sao inteiros , pois t a t b mod n e tc td mod n, aplicando propriedade de somasegue o resultado, em especial temos que

acbd

mod n.

$ Corolario 3 (Produto de congruencias). Se a b mod n e c d mod n entaoa.c b.d mod n. Vale a.c b.c mod n e b.c b.d mod n logo por transitividadea.c b.d mod n.

b Propriedade 7 (Somatorio de congruencias). Se ak = bknk=1

ak =

nk=1

bk

mod n.

mod n k In entao


7

b Propriedade 8 (Produtorio de congruencias). Se ak = bkn

ak =

k=1

n

bk

mod n k In entao

mod n.

k=1

Demonstracao. Por inducao sobre n.

$ Corolario 4. Se a = b mod m entao a = b mod m poisn

n

n

a=

k=1

b Propriedade 9. Se a + c b + c

n

b mod m.

k=1

mod n entao a b mod n

Demonstracao. Pois a + c b c = a b = q.n.

b Propriedade 10. Se at bt

mod n entao a b mod

n.mdc(t, n)

Demonstracao. Vale t(ab) = q.n podemos dividir em ambos lados por mdc(t, n)datn(a b) = q.mc(t, n)mdc(t, n)ntncomo|entao|(a b) de onde segue o resultado.mdc(t, n) mc(t, n)mdc(t, n)

$ Corolario 5. Se mdc(t, n) = 1 entao at bt mod n implica a b mod n.$ Corolario 6. Seja mdc(t, n) = 1 . at bt mod n a b mod n. A parte ) vemdo corolario anterior e ) ja provamos.

Z Exemplo 1. Se mdc(t, n) = 1 e at bt

mod n podemos nao ter a b mod n.

Como e o caso de 4.3 2.3 mod 3 onde t = 3 = n, mdc(t, n) = 3 e nao vale 4 2mod 3 pois 3 |(4 2) = 2.

b Propriedade 11. Se a b

mod m e n|m entao a b mod n.

Demonstracao. a b = q.m e m = t.n da a b = q.t.n que implica a bmod n.

b

Propriedade 12 (Uma relacao com mdc). Se a b mod m entao mdc(a, m) =

mdc(b, m).


8

Demonstracao. Vale que a b = qm, da a = b + q.mmdc(a, m) = mdc(b + q.m, m) = mdc(b, m).

b Propriedade 13 (Uma relacao com mmc). Se a bab

mod mk k In entao

mod mmc(mk )n1 .

Demonstracao. Vale a b = qk .mk , a b e multiplo de cada mk , logo o mnimomultiplo comum deve dividir ele, entao mmc(mk )n1 |a b implicandoa b mod mmc(mk )n1 .

b Propriedade 14. Se a b (mod m)entao

f (a) f (b) (mod m)para qualquer polinomio f de coecientes inteiros. Demonstracao. Sejaf (x) =

n

ak xk

k=0

com ak inteiro para todo k natural.Se a b (mod m) entao ak bk (mod m) para todo k natural e ainda se para todo knatural ak e inteiro, entao ak ak ak bk (mod m), aplicamos a soma em ambos lados comk variando de 0 ate n, da seguen

ak ak

k=0

n

ak bk (mod m)

k=0

logof (a) f (b) (mod m)poisf (a) =

nk=0

k

ak a , f (b) =

nk=0

ak bk .


9

Z Exemplo 2. Calcular o valor de x tal quen

k! x

mod 10

k=1

com n 5.n

k! = 1 + 2 + 6 + 24 +

k=1

b

n

k! 3

mod 10.

k=5

Propriedade 15. Sejam m, n tais que mdc(m, n) = 1 . Se a b mod m e a b

mod n entao a b mod m.n. Demonstracao. Se mdc(m, n) = 1 entao existem x0 , y0 Z tais quemx0 + ny0 = 1multiplicando por a b seguemx0 (a b) +ny0 (a b) = (a b)| {z }| {z }t1 n

t2 m

isso implica que m.n|(a b).

b Propriedade 16. Duas pessoas X e Y

tem idades x e y, com x > y, existe idade em

que a pessoa X tera u vezes a idade de Y x y mod u 1. Demonstracao.

Z Exemplo 3. Duas pessoas X e Y

tem idades x e y, com x > y, queremos saber se

existe alguma idade em que a pessoa X tera u vezes a idade de y e se sim, qual e essaidade.). Supondo que exista uma idade em que a pessoa X tem u vezes a idade de Yentao, existe p natural tal queu(y + p) = x + p uy x = p(1 u) p =

x uyu1

vale que x + p, y + p > 0 pois u > 0 por hipotese, agora x + p e y + p devem ser inteirosx+p=x+

x uyxu x + x uyxu uyu(x y)===u1u1u1u1


10

da mesma maneiray+p=y+

x uyyu y + x uyxy==u1u1u1

portanto u 1|(x y), o fato de y + p ser inteiro, implica que p e inteiro pois y + p = n Z p = n y Z entao se o problema e soluvel vale que x y mod u 1.). Se vale x y mod u 1 entao o problema e soluvel, pois existe t > 0 Z talque x y = t(u 1), tomamos p = t y dau(y + p) = ut = u

(x y)u1

ex+p=xy+t=xy+

(x y)ux uy x + y(x y)u(x y)=== u(y + p)u1u1u1

entao temos a solucao do problema.

1.3

Pequeno teorema de Fermat

Teorema 1 (Pequeno Teorema de Fermat). Sejam p um numero primo, a um inteiro,entaoap a mod p. Demonstracao. Vamos demonstrar primeiro para a natural por inducao, paraa = 0 temos0p = 0 0 mod p.Considerando agora valido para aap a mod p, vamos demonstrar para a + 1 temos( )( )p ( )p1 ( )p kp 0 p kp p(a + 1) =a =a +a +a 1 + ap mod pk0kpk=0k=1p


11

( )ponde abrimos o limite inferior e superior do somatorio e usamos que P |para 1 k kp 1 usando a hipotese temos(a + 1)p 1 + ap 1 + a mod plogo(a + 1)p 1 + a mod p

.

Agora se a e um inteiro negativo e p primo mpar, temos a < 0, a > 0, temos(a)p = ap a mod pque e equivalente aap a mod p, agora se a e inteiro negativo e p = 2 o unico primo par, temos a 0 mod 2 oua 1 mod 2, no primeiro caso a2 0 amod p, no segundo a2 1 a mod p em ambostemosa2 a mod 2logo a demonstracao esta completa.

Z Exemplo 4. Mostre que 42|a

7

a. Pelo pequeno teorema de fermat temos que

7|a7 a, temos tambem que 2|a7 a, falta mostrar que 3|a7 a, mas a7 a = a(a6 1) =a(a3 1)(a3 + 1) = a(a 1)(a + 1)(a2 + a + 1)(a2 a + 1) como temos 3 consecutivos,entao seu produto e divisvel por 6 .

b Propriedade 17. Seja p primo.

Se ap bp mod p entao ap bp mod p2 .

Demonstracao. Pelo pequeno teorema de fermat temos que ap a mod p ,bp b mod p e da hipotese ap bp mod p logo a b mod p ak bk mod p k dab a = (b a)p

p

p1

ak bp1k

k=0p1

k p1k

a b

k=0

p1

ak ap1k pap1 0 mod p

k=0

p1

da segue que p|(a b) e p|Logo ap bp mod p2 .

k=0

ak bp1k logo p2 |(bp ap ).


12

b Propriedade 18. Se mdc(a, p) = 1 entaoap1 1

mod p

com p primo. Demonstracao.Se mdc(a, p) = 1 entao existem x0 , y0 Z tais queax0 + py0 = 1olhando mod p tem-seax0 1.Do pequeno teorema de Fermat temos queap a

mod p

multiplicando por x0 em ambos lados segueap1 ax0 ax0

mod p,

isto e,ap1 1 mod p.

Z Exemplo 5. Calcule o resto da divisao de 1458

333

por 11. Aplicaremos congruencia,

primeiro vericamos que 1458 = 11.132 + 6 da 1458 6 mod 11 o que implica1458333 6333

mod 11

agora aplicamos o pequeno teorema de Fermat de onde sabemos que 610 1 mod 11,pois 11 e primo e mdc(6, 11) = 1, escrevemos 333 = 330 + 3 = 10.33 + 3 logo6333 (610 )33 .63 = 36.6 mod 11porem 36 3 mod 11 e da3.6 18 7 mod 11e conclumos que 1458333 7 mod 11 e por isso deixa resto 7 na divisao por 11.


13

Z Exemplo 6. Calcule o resto da divisao de 7

158

por 13 .

Usamos que mdc(7, 13) = 1, podemos usar queap1 1

mod p

712 1

mod 13

com p = 13 e a = 7, logo

158 = 12.13 + 2logo

7158 (|{z}712 )13 .72 = 49 = 3.13 + 10 10 mod 13,1

logo o resto da divisao e 13 .

Z Exemplo 7. Descobrir N = 0 um numero de tres dgitos tal que N

2

= N + b.103 ,

sendo que N e um numero par .Tomamos N = a2 a1 a0 = a2 102 + a1 .10 + a0 logo

(a2 102 + a1 .10 + a0 )2 = a2 102 + a1 .10 + a0 + b.103tomando a congruencia mod 10, tem-sea20 a0

mod 10

com a0 par podemos vericar que a0 = 0 ou a0 = 6, se a0 = 0 podemos concluirtomando congruencias

mod 102 e

mod 103 que a1 = a2 = 0 logo N = 0 o que nao

queremos. Entao a0 = 6, tomando congruencia mod 102 segue

N 2 (a1 .10 + 6)2 = a1 .10 + 6

mod 102


14

da expandindo o termo ao quadrado e anulando termos multiplos de 102 segue2.6.a1 .10 + 62 2a1 .10 + 62 a1 .10 + 6

mod 102 a1 .10 30 70 mod 102

o que implica a1 = 7 . Agora analisando mod 103 segue

N 2 (a2 .102 + 76)2 = a2 102 + 76 expandindo o quadrado e usando mod 103 , tem-se6.2 a2 .102 + 762 2.a2 .102 + 762 a2 102 + 76 2a2 .102 . |{z}76 +762 |{z}70+6

10+2

a2 102 76 762 = 5700 700 300 mod 102por isso a2 = 3 e temos portanto que N = 376 , seu quadrado e N 2 = 141 376.

1.4m

Aneis zn.

Denicao 4 (Adicao e multiplicacao em Zn ). Sejam n 2, a, b Z, denimos a

adicao + como a operacao que faza+b=a+be a multiplicacao . comoa.b = a.b.Caso que claro que estamos operando em Zn algumas vezes iremos omitir a barrasobre o elemento b, escrevendo apenas b.

b

Propriedade 19. A adicao e multiplicacao nao dependem dos representantes das

classes residuais. Demonstracao. Se a a mod n e b b mod n entaoa + b a + b

mod n a + b = a + b a + b = a + b = a + b = a + b .

O mesmo para o produto.


15

Simbolizaremos a estrutura (Zn , +, .), isto e, o conjunto Zn munido das operacoesdenidas acima apenas como Zn . Denotaremos Tal conjunto por Zn ou zn .

b Propriedade 20. Zn e um anel comutativo com unidade. Demonstracao. Propriedades da adicao Existe elemento neutro 0, tal que 0 + m = m pois 0 + m = 0 + m = m. Existencia do simetrico. Para a existe a tal que a + a = 0. Se se a n entao

existe t N tal que a + t = n e da a + t = 0 = a + t, portanto a = t, se a > n ,a e representado por b onde b < n e aplicamos o mesmo processo anterior. Comutatividade a + b = a + b = b + a = b + a. Associatividade

(a + b) + c = (a + b) + c = a + (b + c) = a + (b + c) = a + (b + c).Temos com isso um grupo abeliano (Zn , +). Vejamos agora as propriedades da multiplicacao Existe elemento neutro 1, tal que 1.m = m pois 1.m = 1.m = m. Comutatividade a.b = a.b = b.a = b.a. Associatividade

(a.b).c = (a.b).c = a.(b.c) = a.(b.c) = a.(b.c).Agora a propriedade que relaciona a adicao e multiplicacao, a distributividade.

(a + b)c = (a + b)c = ac + bc = ac + bc = a.c + b.c

b Propriedade 21. Um elemento a Zn e invertvel mdc(a, n) = 1. Demonstracao. ). Se a Zn e invertvel entao existe b Zn tal que ab = 1,da a.b 1 mod n n|ab 1 tn = ab 1 para algum t Z, (t)n + ab = 1 damdc(a, n) = 1.). Se mdc(a, n) = 1, entao existem x, y Z tais que ax + ny = 1, olhando em zn ,ax = 1 portanto a e invertvel.


16

b Propriedade 22. m gera Zn m e invertvel em Zn. Demonstracao.). Se m gera Zn entao existe n N tal que n.m = 1, portanto m e invertvel.). Se m e invertvel entao mdc(m, n) = 1 da existem x0 , y0 Z tais que x0 m+y0 n =1, sendo t um elemento arbitrario de Z tem-setx0 m + ty0 n = tolhando sobre a congruencia mod n tem-se (tx0 )m = t, portanto m gera Zn .

b Propriedade 23. Zn e corpo n e primo. Demonstracao. ). Vamos usar a contrapositiva de zn e corpo entao n e primoque e: se n nao e primo entao zn nao e corpo. Se n nao e primo entao existem a, b Ztais que a.b = n com 1 < a, b < n, daab = n = 0com a, b fora da classe do 0, da Zn nao e domnio , nao vale a lei do corte, portanto Znnao e corpo.). Se n e primo, entao vale mdc(a, n) = 1 para todo 0 < a < n em Z, portanto pelapropriedade anterior a invertvel para todo elemento nao nulo, portanto Zn e corpo.

b Propriedade 24. O quadrado de um numero inteiro tem um dos seguintes algarismosde unidade {0, 1, 4, 5, 6, 9}. Demonstracao.Analisamos em Z10


17

a

a2

0

0

1

1

2

4

3

9

4

16 = 6

5

25 = 5

6

36 = 6

7

49 = 9

8

64 = 4

9 81 = 1

Z Exemplo 8. Pelo lema de Euclides mdc(a, b) = mdc(a, b ta), tomamos a = k,b = n e t = 1 da mdc(k, n) = mdc(k, n k) = 1tal fato pode ser usado em problemas para determinar inversos em um anel Zn .

b

Propriedade 25. Em zp com p primo, os unicos numeros que sao inversos de si

mesmos sao p 1 e 1 . Demonstracao. Seja x2 = 1, entao (x 1)(x + 1) = 0, o que implica x = 1 oux = 1 p 1.

$ Corolario 7. Em Zp com p > 2 primo, o unico elemento que possui ordem 2 e p 1,ja vimos que (p 1)(p 1) = 1 o elemento 1 possui ordem 1.

Z Exemplo 9. Quando n nao e primo, em Z

n

podem existir outros elementos que nao

sao 1 e n 1 que satisfazem x2 = 1.Por exemplo em Z4k+4 vale (2k + 2)2 = 1.(2k + 2)2 = 4k 2 + 4k + 1 = 4k (4k + 4) +1 = 1.| {z }=0

1.4.1

Teorema de Wilson

b Propriedade 26 (Teorema de Wilson). p e primo (p 1)! 1

mod p.


18

Demonstracao. ). Para p = 2 a propriedade vale, suponha entao p > 2, pprimo. Tome A = {2 k p 2, k N }, valep2

k1

mod p

k=1

pois para cada k A existe k = k A tal que k.k 1 mod p, dap1

k p 1 1 mod p

k=1

entao(p 1)! 1

mod p.

).Se n = st e composto entao vale (n1)! 0 mod n pois s e t aparecem como fatores (sesao distintos), caso sejam fatores iguais , inicialmente para n = 4 temos 3! = 3.2 = 6 2mod 4 e para s > 2 vale s2 1 > 2s logo (s2 1)! 0 mod s2 , pois s e 2s aparecemcomo fator, em qualquer caso se n e composto nao vale (n 1)! 1 mod n.

$ Corolario 8. Vale quen (s+1)p1

k (1)n+1

mod p

s=0 k=sp+1

onde p e primo .p1n

(k + sp) 24

(k)

s=0 k=1

s=0 k=1

Z Exemplo 10. Z

p1n

n

(1) (1)n+1

mod p

s=0

possui (24) = (8.3) = (8)(3) = (23 22 )(3 1) = 4.2 = 8

elementos, que sao os elementos n, tais que mdc(n, 21) = 1, 0 < n < 24, n N .Sendo1, 5, 7, 11, 13, 17, 19, , 23Todos elementos diferentes da identidade tem ordem 2, pois

52 = 25 = 24+1, 72 = 49 = 2.24+1, 112 = 121 = 5.24+1, 132 = 169 = 7.24+1, 172 = 289 = 12.24+1, 1e 23 sabemos que tem ordem 2.


Z Exemplo 11. Z

10

19

e um grupo cclico. Z10, possui (10) = 4 elementos, eles sao

1, 3, 7, 9 pois 1.1 = 1, 3.7 = 21 1 e 9.9 = 81 1. O grupo e gerado por 3, pois 32 = 9. 33 = 9.3 = 27 7 34 = 33 .3 = 7.3 = 21 1Entao < 3 >= Z10. O numero de divisores de 4 e 3, que sao os numeros 1, 2 e 4. Entao

ele possui apenas um grupo nao trivial com 2 elementos, que e < 9 >, da segue tambemque < 3 >=< 7 >= Z10.

Z Exemplo 12. Z

8

nao e um grupo cclico. O numero de elementos desse grupo e

(8) = 4, entao ele possui subgrupos com 1, 2, 4 elementos. Os elementos do grupo sao Triviais 1 e 7. Nao triviais: 3 pois 3.3 = 9 1. 5 pois 5.5 = 25 1. Logo o grupo e {1, 3, 5, 7} = Z8 nao e cclico.

Z Exemplo 13. Z

17

e um grupo cclico. Tal grupo possui (17) = 16 elementos,

os divisores de 16 sao 1, 2, 4, 8, 16, ele possui entao 5 subgrupos, com respectivamente1, 2, 4, 8, 16 elementos. < 1 >= {1} e subgrupo trivial 3 gera o grupo pois

32 = 933 = 1034 = 1335 = 5


20

36 = 1537 = 1138 = 1639 = 14310 = 8311 = 7312 = 4313 = 12314 = 2315 = 6 Possui 2 (17) = 8 geradores. Que sao dados por 3s com mdc(16, s) = 1.

33 = 1035 = 537 = 1139 = 14311 = 7313 = 12315 = 6 Subgrupos de ordem 8, temos que saber s tal que mdc(16, s) = 2, tais valores sao

2, 6, 10, 1432 = 936 = 15310 = 11314 = 2.


21

Subgrupos de ordem 4, temos que saber os valores de s tais que mdc(16, s) = 4, tais

valores sao 4 e 12 os elementos sao34 = 13312 = 4. Subgrupos de ordem 2, mdc(16, s) = 8, apenas para s = 8 e o elemento e

38 = 16.

1.5

Aplicacoes de congruencias

1.6

Congruencia e divisibilidade

Z Exemplo 14. o quadrado de um numero deixa sempre resto 0, 1 ou 4 na divisaopor 5. Analisamos pela seguinte tabela, usando congruencia mod 5 .a

0

1

2

3

4

a2

0

1

4

4

1

Z Exemplo 15. Descobrir os valores de n tais que

n

k! e quadrado perfeito .

k=1

Por inspecao podemos observar que n = 0, 1, 3 resultam tem 0, 1, 9 e os valores comn = 2, 4 nao geram quadrados perfeitos, se n 5 temosnk=1

k! =

4

k! +

k=1

nk=5

k!

4

k!

mod 5

k=1

logo para os valores n 5 nao temos quadrados perfeitos.

Z Exemplo 16. Mostrar que 9|9|(10

n

+ 3.4n+2 + 5) para todo n natural. Em Z9 val

que 10n = 1, da temos10n + 3.4n+2 + 5 = 1 + 34n + 5 = 6 + 3.4n = 3(2 + 4n )como 2 + 4n 2 + 1 = 3 mod 3 entao a expressao entre parentheses e divisvel por 3 ea expressao pedida e divisvel por 9.


22

Z Exemplo 17. Mostrar que para n mpar vale7|(22n+1 + 3n+2 ).Substituindo n = 2s + 1 camos com

24s+3 + 32s+3 = (24 )s .8 + 9s 9.3 2s + (1)2s 0

mod 7

onde usamos 16 2 mod 7, 9 2 mod 7, 8 1 mod 7 e 6 1 mod 7.

Documents

congruenciaeaneizn