algor da divisao1-2

Prévia do material em texto

Algoritmo da Divisão em Z (1)Z (1)Z (1)Z (1) 
Dados dois inteiros D e 0≠d existem e são únicos os inteiros q e r tal 
que rqdD += . onde dr <≤0 . 
Prova: 
Antes vamos enunciar o Teorema de Eudoxius1: Dados D e d inteiros com 
0≠d então D é múltiplo de d ou se encontra entre dois múltiplos consecutivos 
de d , isto é, a cada par de inteiros D e 0≠d existe um inteiro q tal que: 
Se 0>d , dqDqd )1( +<≤ ; 
Se .)1(,0 dqDqdd −<≤< 
 
Agora a demonstração do Algorítmo: 
 
Suponhamos inicialmente, 0>d . Então pelo teorema de Eudoxius, existe q 
satisfazendo 
dqDqd )1( +<≤ 
o que implica .0 dqdD <−≤ Dessa forma se definirmos qdDr −= , teremos 
garantida a existência de q e .r Devemos agora mostrar que são únicos. Vamos 
então supor que existem outros 1q e 1r verificando: 
 
11 rdqD += com .0 1 dr <≤ 
 
 Assim, ).()( 11111 rrdrrdqqrdqrdq −⇒−=−⇒+=+ Mas, como 
dr <≤ 10 e dr <≤0 logo drr <−1 e portanto como )( 1 rrd − , 
rrrr =⇒=− 11 0 . Como rr =1 , qqqddq =⇒= 11 pois .0≠d 
 
 Observe que se 0<d , usando a parte do teorema de Eudoxius relativa a 
0<d teríamos sem problemas a demonstração do teorema.  
 
1
 Esse resultado costuma ser erroneamente atribuído a Arquimedes e chamado “Princípio de Arquimedes”. 
 
Algoritmo da Divisão em Z (2)Z (2)Z (2)Z (2) 
Dados dois inteiros D e 0≠d existem e são únicos os inteiros q e r tal 
que rqdD += . onde dr <≤0 . 
Prova: 
 Suponhamos inicialmente que 0>d e consideremos o conjunto 
S= }:{ ZxNdxD ∈∈− . 
 Observe que S ∅≠ pois se tomarmos Dx −= , teremos um elemento em 
S. Como S é subconjunto de N e é diferente do vazio , S tem um menor elemento. 
Seja r esse elemento. Assim, 0≥r e dqDr −= , ou seja, .rdqD += 
 Devemos então ainda mostrar que dr < . Suponhamos por absurdo que 
dr ≥ . Então existe em Z `r tal que drr += ` , isto é, rr <` e portanto ∉`r S. Mas por 
outro lado, )1(` +−=−−=−= qdDddqDdrr o que é um absurdo pois `r seria 
elemento de S. Assim, .dr < 
 Para o caso em que 0<d , existem números ``, rq tais que 
`)`(`)`( rqdrdqD +−=+−= com bdr −<≤ `0 Portanto basta escolher `qq −= e `rr = 
para demonstrarmos o teorema. 
 
Devemos agora mostrar que são únicos. Vamos então supor que existem 
outros 1q e 1r verificando: 
11 rdqD += com .0 1 dr <≤ 
 
 Assim, ).()( 11111 rrdrrdqqrdqrdq −⇒−=−⇒+=+ Mas, como 
dr <≤ 10 e dr <≤0 logo drr <−1 e portanto como )( 1 rrd − , 
rrrr =⇒=− 11 0 . Como rr =1 , qqqddq =⇒= 11 pois .0≠d