Algoritmo da divisão euclediana

[Thiago Manhães Lima]

A soma dos quocientes a divisão euclidiana de dois números D e D' por um número d > 0 é sempre igual ao quociente da divisão D + D' POR d? Se não for igual de quanto difere?

[Rui Carpentier]

A soma dos quocientes a divisão euclidiana de dois números D e D' por um número d > 0 é sempre igual ao quociente da divisão D + D' POR d?

Não, faça D=D'=3 e d=2. O quociente de 3 (i.e. D ou D') por 2 (i.e. d) é 1 enquanto o quociente de 6 (i.e. D+D') por 2 é 3, e no entanto \(3\not=1+1\).

Se não for igual de quanto difere?

Pense no que significa o quociente. O número \(q\) é quociente de \(D\) por \(d\) se \(D=qd+r\) com \(0\leq r \leq d-1\).
Assim, se \(q\) é quociente de \(D\) por \(d\), \(q'\) é quociente de \(D'\) por \(d\), e \(q''\) é quociente de \(D+D'\) por \(d\), então \(D=qd+r\), \(D'=q'd+r'\) e \(D+D'=q''d+r''\) com \(r,r',r''<d\). Destas equações tiramos que \(D+D'=(q+q')d+r+r'=q''d+r''\), ou seja \((q''-q-q')d=r+r'-r''\). Como \(r,r',r''<d\Rightarrow -d<r+r'-r''<2d\) temos que \(q''-q-q'\) só pode tomar os valores 0 ou 1.

[Thiago Manhães Lima]

A soma dos quocientes a divisão euclidiana de dois números D e D' por um número d > 0 é sempre igual ao quociente da divisão D + D' POR d?

Não, faça D=D'=3 e d=2. O quociente de 3 (i.e. D ou D') por 2 (i.e. d) é 1 enquanto o quociente de 6 (i.e. D+D') por 2 é 3, e no entanto \(3\not=1+1\).

Se não for igual de quanto difere?

Pense no que significa o quociente. O número \(q\) é quociente de \(D\) por \(d\) se \(D=qd+r\) com \(0\leq r \leq d-1\).
Assim, se \(q\) é quociente de \(D\) por \(d\), \(q'\) é quociente de \(D'\) por \(d\), e \(q''\) é quociente de \(D+D'\) por \(d\), então \(D=qd+r\), \(D'=q'd+r'\) e \(D+D'=q''d+r''\) com \(r,r',r''<d\). Destas equações tiramos que \(D+D'=(q+q')d+r+r'=q''d+r''\), ou seja \((q''-q-q')d=r+r'-r''\). Como \(r,r',r''<d\Rightarrow -d<r+r'-r''<2d\) temos que \(q''-q-q'\) só pode tomar os valores 0 ou 1.

[Thiago Manhães Lima]

Obrigado meu amigo, eu só não entendi o final quando vc diz -d,r+r'-r''<2d e conclui que q"-q-q' só pode assumir valores 0 ou 1?

[Thiago Manhães Lima]

amigo, eu já entendi o porque dos valores assumidos por q"-q-q' só inda não entendi foi -d<r+r'-r"<2d

[Rui Carpentier]

amigo, eu já entendi o porque dos valores assumidos por q"-q-q' só inda não entendi foi -d<r+r'-r"<2d

É usar o facto de que a soma perserva as desigualdades: \(a<b ~,~ c\leq d \Rightarrow a+c<c+d\).

Assim,

\(\left\{\begin{array}0\leq r <d\\0\leq r' <d\\0\leq r'' <d\end{array}\right. \Rightarrow \left\{\begin{array}0\leq r <d\\0\leq r' <d\\-d<-r'' \leq 0\end{array}\right. \Rightarrow -d<r+r'-r"<2d\)