Zé Moleza | TCC, monografias e trabalhos feitos. Pesquise já!

Você está em Trabalhos Acadêmicos > Exatas > Informática

Favoritos Seus trabalhos favoritos: 0


Publicidade

Trabalho em Destaque

Título: A Proteção Social

1 INTRODUÇÃO O nascedouro foi em 1883, na Alemanha com o Chanceler Bismarck. Foi um marco tanto da Seguridade Social como da Previdência Social (primeiro sistema escrito de previdência social – seguro social). A forma de contribuição ou custeio para…


Publicidade

A Divisibilidade e a Congruência dos Números Voltado para a Informática.

Trabalho enviado por: Silvia Aparecida Machado da Silva

Data: 06/06/2003

Um conceito chave em Teoria dos Números é o conceito de divisibilidade. Enquanto nos números reais, por exemplo, pode-se dividir qualquer número por outro (não nulo), obtendo como resultado um número real, nos inteiros é diferente. Um inteiro a só é divisível pelo inteiro b quando existir um inteiro c tal que a = b c. Nesse caso, diz-se também que b é um divisor de a, ou que b divide a, ou ainda que a é múltiplo de b.

Por exemplo, 4 é divisível por 2, mas não é por 3. Mesmo que a não seja divisível por b, pode-se sempre encontrar, de modo único, inteiros c (quociente) e r (resto) tais que a = b c + r, com 0 < r < b.

Definição:

Sejam a e b números inteiros com a não nulo. Dizemos que a divide b (ou que b é divisível pôr a, ou ainda, que b é múltiplo de a se existe um inteiro c tal que b = a × c.

Notação:

a | b para indicar que a divide b. Chamamos a de divisor de b.

O inteiro c nas condições da definição é único. De fato, se existisse outro d tal que b = ad, então teríamos que ac = ad, logo (como a ¹ 0) c = d.

O inteiro assim definido c é chamado de quociente de b por a.

"0" possui infinitos divisores positivos e os inteiros 1 e -1 possuem um único divisor positivo.

Proposição:

Para quaisquer inteiros a, b, c e d (lembrando que os divisores são sempre não nulos), temos que:

Para todo inteiro a tem-se que a|a

Se a|b e b|c, então a|c

Se a|b e c|d, então a × c | b × d

Se a|b e a|c, então a | b + c

Se a|b, então para qualquer n Î , tem-se que a | b × n

Se a|b, e a|c, então para quaisquer m e n Î , tem-se que a | (b × m + c × n).

Divisibilidade e resto

Sejam a e b números inteiros com a não nulo. Então, existem inteiros q e r, únicos, tais que:

b = a × c + r, com 0 £ r < |a|.

Os números q e r são chamados de quociente e resto, da divisão de a pôr b.

Um termo que é dado pela noção de divisibilidade é a de máximo divisor comum (mdc) que definimos a seguir.

Definição:

Sejam a e b números inteiros. Dizemos que um número inteiro d é o máximo divisor comum de a e b se e somente se d|a e d|b e para qualquer inteiro c que divide a e b tem-se que c|d.


Teorema de Bezout

Sejam a e b números inteiros com d = mdc(a, b).

Então, existem inteiros r e s tais que d = a × r + b × s.

Aplicação do Teorema:

Proposição:

Sejam a, b números inteiros, mdc(a, b) = d, e c um inteiro qualquer.

Então mdc(a × c, b × c) = d × |c|.


Teorema de Euclides

Sejam a, b e c números inteiros tais que a | b × c. Se mdc(a, b) = 1, então a|c.

Definição:

Dois números inteiros a e b são ditos relativamente primos se mdc(a, b) = 1.

Donde segue o seguinte resultado:

Proposição:

Sejam a e b números inteiros relativamente primos e c outro inteiro.

Se a ½ c e b ½ c, então a × b ½ c.

Definição de mínimo múltiplo comum:

Definição:

Sejam a e b números inteiros. Dizemos que um número inteiro m é o mínimo múltiplo comum de a e b se e somente se a | m e b | m e para qualquer inteiro m' tal que a | m' e b | m', então m | m'.

Proposição :

Sejam a e b números inteiros, d = mdc(a, b) e m = mmc(a, b).

Então, m × d = |a × b|.

Finalmente, a definição de número primo e o enunciado do teorema fundamental da aritmética.

Definição:

Um número inteiro positivo p é chamado de primo se possui dois únicos divisores positivos 1 e | p |.

Teorema Fundamental da Aritmética

Seja a um inteiro diferente de 0, 1 e -1.

Então, existem primos positivos p1 < p2 < ... < pr e inteiros n1, n2, ..., nr tais que:

a = S × (p1)n1 + (p2)n2 + ... + (pr)nr, com S = ± 1, conforme a seja positivo ou negativo.

Além disso, esta decomposição é única.


Noções básicas de congruência:

O que são números perfeitos:

Os chamados números perfeitos são números cuja soma de seus fatores resulta no valor do próprio número. (6 = 1, 2, 3 / 1 + 2 + 3 = 6).

Euclides: n da forma (2 n – 1)* 2(n-1 ) é um número perfeito, se o fator (2 n – 1) for um número primo. Assim, para n = 2, 3, 5 ou 7, a expressão (2 n – 1) assume os valores 3, 7, 31 ou 127 – os quais são também primos.

Para esses valores, podem-se obter o números perfeitos 6, 28, 496 e 8128.

O que são números primos:

São números cujos fatores são apenas um e o próprio número, ou seja, não têm outros divisores.

Pôr fim, um número primo é um inteiro n>1 que não é divisível por nenhum inteiro positivo diferente de 1 e de n.

Referências a eles: proposição 20, do capítulo IX dos "Elementos" - de Euclides - onde é apresentada a prova de que os números primos são infinitos.

Esses fatos - a restrita divisibilidade, e sua infinitude – detêm características que garantem nteressantes propriedades a determinados algoritmos aplicados a Criptografia.

O...

Para ver o trabalho na íntegra escolha uma das opções abaixo

Login

Ou faça login



Login

Crie seu cadastro




English Town