Apostila de Divisibilidade e algoritmo

Prévia do material em texto

LICENCIATURA EM MATEMÁTICA
DISCIPLINA: Estruturas Algébricas I
PROFESSORA: Msc. Ivone Cristina Barros Pedroza
DIVISIBILIDADE
DIVISIBILIDADE
Em nossa educação básica, aprendemos que, quando um número inteiro é dividido por um número inteiro não nulo, o quociente pode ou não ser um número inteiro. Esta observação nos leva a seguinte definição.
Definição 1: Um número inteiro “d” divide um número inteiro “a”, se “a” é múltiplo de “d”, então existe um número inteiro “c” tal que . Neste caso, o inteiro “c é chamado quociente de “a” por “d” é indicado por 
Quando “d”divide “a” denotamos por:
Quando “a”é múltiplo de “d”dizemos também que “a”é divisível por “d” ou que “d” divide “a”.
Quando “d” não divide “a”, escrevemos . Não escreva e nem para denotar que “d” divide “a”. A notação correta é: , esta relação é chamada de DIVISIBILIDADE EM .
Exemplo 1: Veja as seguintes Divisibilidades em .
7 divide 161, pois existe um inteiro, 23, tal que 
15 divide 3150, pois, podemos encontrar um número inteiro q, a saber, , tal que . Podemos escrever que: 15 divide 3150, ou que 15 é divisor de 3150 ou ainda que 3150 é múltiplo de 15.
.
Note também que se então , e 
Agora apresentamos em forma de proposição algumas das propriedades do conceito de divisibilidade. Sugiro que antes de proceder as demonstrações, tente ilustrar com números o que cada propriedade diz. Desse modo estará familiarizado com os resultados quando for demonstrar.
Lema: Sejam , temos:
Se , então para qualquer combinação linear de a e b com coeficientes .
(Limitação). Se , então 
(Transitividade). Se , então 
Em particular, segue do lema (a) que: 
Se , então 
Se , então 
Vejamos como utilizar essas propriedades para resolver alguns problemas de divisibilidade.
Exemplo 1: Encontre todos os naturais a e b tais que .
Exemplo 2: Mostre que é múltiplo de 7, se e somente se é múltiplo de 7.
Exemplo 3: Mostre que se então 
Exemplo 4: Qual é o maior inteiro n para qual é divisível por ?
 
Exemplo 5: Demonstre que sabendo que m e n são números pares.
Solução:
Sabemos que m e n se tratam de números pares, então existem tal que:
ou seja, m e n são números pares é equivalente a afirmar que m e n são divisíveis por 2. Devemos mostrar que, se:
Portanto: 
 
Exemplo 6: Usando o principio da indução finita e considerando , prove que:
Solução:
		Aqui a afirmação A(n), que queremos provar ser verdadeira para cada inteiro é a seguinte: 
	Assim:
A (0): 
A (2): 
A (3): e assim por diante.
BASE – Vamos verificar a base da indução. Isto é, que é o mesmo que verificar A (0) é verdadeira. Para isso, basta observar que: 
HIPÓTESE DE INDUÇÃO – Vamos supor que para n = k, seja então k um inteiro, e admitamos a hipótese de indução, de que A(k) é verdadeira, ou seja, de que 
Por hipótese de indução temos que se: um número tal que:
TESE - Agora, provaremos que para , ou seja, , temos:
Portanto é um múltiplo inteiro de 7, ou seja, também é divisível por 7. Sendo assim, provamos, pelo Princípio de Indução Finita, que é válida para cada , ou seja, que para cada .
ALGORITMO DE EUCLIDES
Até agora tratamos em detalhes as divisões exatas entre elementos do conjunto . A partir de agora vamos estudar a fundo aquelas divisões que tem resto. Definiremos um método de divisão entre quaisquer números inteiros, desde que o divisor seja um numero não nulo. Este é o espaço do Algoritmo de Euclides (ou Algoritmo da Divisão), cujo nome é devido aos estudos do matemático grego Euclides (aproximadamente 330 a. C a 270 a. C).
Teorema 1: Algoritmo de Euclides ou Algoritmo da Divisão: Para quaisquer inteiros positivos “a” e “b” com , existem e são únicos o par de inteiros que satisfazem as seguintes condições: 
Os números “q” e “r” são chamados “q” (quociente) e “r” (resto), da divisão de “a” por “b”.
OBS: Os elementos que aparecem no teorema acima são chamados de dividendo, divisor quociente e resto na divisão euclidiana de “a” por “b”, respectivamente.
Uma notação para o algoritmo da divisão
Se “a” e “b” são números naturais, com , e se “q” e “r” são números naturais como o teorema anterior, denotaremos simbolicamente: 
a
 b
 
r
 q
Onde: 
a – dividendo
b – divisor
q – quociente
r – resto
Podemos observar facilmente por meio de alguns exemplos que o teorema não é válido se .
Exemplo 7: Algoritmo de Euclides
Para temos, , pois .
Para temos, , pois 54.
Paridade de um inteiro
Fixado um inteiro positivo “d”, em várias instancias, na teoria dos números, classificamos os números inteiros pelos restos da divisão por “b”. 
Por exemplo, se , então o resto da divisão de qualquer inteiro “a” por 2 satisfaz .
Para , temos que: , dizemos que “a” é um inteiro par. 
Para , temos que: , dizemos que “a” é um inteiro impar.
De forma análoga se temos . 
Para , temos que: , dizemos que “a” é um inteiro par. 
Para , temos que: , dizemos que “a” é um inteiro ímpar.
Para , temos que:, dizemos que “a” é um inteiro par. 
Para , temos que:, dizemos que “a” é um inteiro ímpar.
Em geral, para , obtemos:
OBS: Os “n” conjuntos:
Chamam-se as classes de resto módulo n.
Exemplo 8: Encontrar 5 números ímpares cuja soma é 100. 
Exemplo 9: Um tabuleiro quadrado de 5x5 pode ser totalmente coberto por dominós?
Exemplo 10: Mostrar que, se “a” é um inteiro qualquer, então um dos inteiros é divisível por 3.
OBS: Como encontrar “q” e “r” na divisão euclidiana?
Caso : Como , temos que 
Caso : Neste caso, tomamos 
Caso : Podemos considerar a sequencia: 
Podemos considerar que “a” está situado entre dois múltiplos consecutivos de “b”
Assim obtemos e, portanto 
Exemplos de Algoritmo de Euclides
Exemplo 11: Encontrar o quociente “q” e o resto “r” na divisão euclidiana de e . Analise também os casos de , e 
Exemplo 12: Na divisão euclidiana do inteiro por um inteiro positivo “b”, o quociente é 12 e o resto é “r”. Encontre os valores de “b” e de “r.