2012/10/3 terence thirteen <peterdirich...@gmail.com> > Em 3 de outubro de 2012 06:12, ennius <enn...@bol.com.br> escreveu:>> > Caros Colegas,>> Gostaria de obter, se possível for, demonstração do > teorema abaixo, em que> divisão quer dizer divisão euclidiana, n é inteiro, > D e d são inteiros> positivos.>> Teorema: O quociente da divisão de n por > Dd é igual ao quociente da divisão> de q por d, sendo q o quociente da > divisão de n por D. > O quociente de x por y é [x/y], parte inteira da divisão. > Você quer que [n/Dd] = [[n/D]/d] > Eu tenho boas razões para pensar que isso não é verdadeiro, pelo menosnão > sem impor alguma restrição a D e d. >
Isso é verdadeiro. [n/Dd] = [[n/D]/d] sse d[n/Dd] = d[[n/D]/d] (para d != 0) d[[n/D]/d] = [n/D] - [n/D]%d, onde a%b é o resto de a na divisão por b. De modo similar d[n/Dd] = d[(n/D)/d] = (n/D) - (n/D)%d Note que o resto aqui é especial aqui, pq carrega também a mantissa do número. (n/D)%d = ([n/D] + m)%d = [n/D]%d + m, onde m é a mantissa, ou seja a parte fracionária do número. Assim fica claro que (n/D) - (n/D)%d = [n/D] - [n/D]%d Isso é um exercício do Art of Computer Programming do Knuth. -- []'s Lucas
