Divisão euclidiana: quociente, resto e usos em código

O algoritmo da divisão é o resultado que garante que, dados dois inteiros a e b com b diferente de zero, existem um único quociente q e um único resto r tais que a = b · q + r, com 0 ≤ r < |b|. É a formalização da “conta de dividir” que se aprende na escola, só que escrita de um jeito preciso o bastante para servir de base à teoria dos números e à programação.

Neste artigo você vai ver o enunciado, a demonstração intuitiva, exemplos com números positivos e negativos, como o algoritmo aparece em código e onde ele é usado de verdade: do máximo divisor comum à criptografia.

O enunciado do algoritmo da divisão

Também chamado de divisão euclidiana, o teorema diz:

Para todo inteiro a e todo inteiro b ≠ 0, existem inteiros únicos q e r tais que a = b · q + r e 0 ≤ r < |b|.

Os nomes das partes são os mesmos da escola:

• a é o dividendo;
• b é o divisor;
• q é o quociente;
• r é o resto.

O ponto importante é a palavra “únicos”. A condição 0 ≤ r < |b| é o que impede que existam várias respostas. Sem ela, 17 = 5 · 2 + 7 também seria verdade, mas 7 não é um resto válido porque é maior que 5.

Por que o resultado é verdadeiro

Existência

A ideia é simples. Considere o caso a ≥ 0 e b > 0. Subtraia b de a repetidamente enquanto o resultado for maior ou igual a b. Em algum momento você para, porque os números vão diminuindo e não podem ficar negativos indefinidamente. O número de subtrações é q, e o que sobrou é r, que obrigatoriamente fica entre 0 e b − 1.

Formalmente, a demonstração usa o princípio da boa ordenação: o conjunto dos valores não negativos da forma a − b · k tem um menor elemento, e esse menor elemento é o resto.

Unicidade

Suponha que existam dois pares (q, r) e (q’, r’) que funcionem. Subtraindo as equações, obtemos b · (q − q’) = r’ − r. O lado direito tem valor absoluto menor que |b|, mas o lado esquerdo é um múltiplo de b. O único múltiplo de b com valor absoluto menor que |b| é zero. Logo q = q’ e r = r’.

Exemplos resolvidos passo a passo

O caso dos números negativos

O exemplo com −17 é onde muita gente erra. A tentação é dizer q = −3 e r = −2, mas o resto não pode ser negativo. Para manter 0 ≤ r < 5, o quociente precisa ser −4, e o resto fica 3. Regra prática: quando o dividendo é negativo e a divisão não é exata, o quociente “desce” uma unidade e o resto vira b − (resto que você esperaria).

Quando o resto é zero

Se r = 0, dizemos que b divide a. É a definição de divisibilidade, e é daí que saem conceitos como múltiplos, números primos e fatoração.

O algoritmo da divisão na programação

Quase toda linguagem tem operadores para quociente e resto, mas cuidado: eles nem sempre seguem a definição matemática quando há números negativos.

# Python: // e % seguem o piso, resto tem o sinal do divisor
print(-17 // 5, -17 % 5)   # -4 3
print(divmod(17, 5))       # (3, 2)

// JavaScript: % mantém o sinal do dividendo
console.log(-17 % 5);                 // -2
const mod = (a, b) => ((a % b) + b) % b;
console.log(mod(-17, 5));             // 3

Em C, Java e JavaScript, a divisão inteira trunca em direção a zero, então o resto pode sair negativo. Em Python, o resto acompanha o sinal do divisor. Para divisor positivo, isso coincide com a divisão euclidiana. Quando o resto precisa ser sempre não negativo (índices de vetores circulares, por exemplo), use uma função auxiliar como a mod acima.

Uma implementação didática, por subtrações sucessivas, deixa a ideia bem visível:

def divisao(a, b):
    # assume a >= 0 e b > 0
    q = 0
    while a >= b:
        a -= b
        q += 1
    return q, a

Esse tipo de construção é um bom exercício para quem está estudando algoritmos e lógica de programação, e pode ser reescrita de forma recursiva, como mostramos no texto sobre algoritmo recursivo.

Aplicações práticas

1. MDC pelo algoritmo de Euclides: aplica a divisão repetidamente, trocando (a, b) por (b, r) até o resto ser zero. O último divisor não nulo é o MDC.
2. Aritmética modular: relógios, dias da semana e hashes usam o resto da divisão.
3. Criptografia: sistemas como o RSA dependem de operações com resto em números muito grandes.
4. Conversão de bases: para passar um número para binário, você divide por 2 repetidamente e lê os restos de trás para frente.
5. Verificação de paridade e dígitos verificadores: par ou ímpar é só o resto da divisão por 2.

Exemplo com o algoritmo de Euclides

MDC(252, 105): 252 = 105 · 2 + 42; 105 = 42 · 2 + 21; 42 = 21 · 2 + 0. Logo, MDC = 21.

def mdc(a, b):
    while b:
        a, b = b, a % b
    return a

Erros comuns ao aplicar o teorema

• Aceitar resto negativo ou maior que o divisor.
• Esquecer que o divisor não pode ser zero.
• Confundir o operador % da linguagem com o resto matemático.
• Achar que o quociente de −17 por 5 é −3 na divisão euclidiana.

Perguntas frequentes

Qual a fórmula do algoritmo da divisão?

a = b · q + r, com 0 ≤ r < |b|. Dividendo é igual a divisor vezes quociente mais resto.

Por que se chama algoritmo se é um teorema?

O nome é histórico. O enunciado é um teorema, mas a prova de existência descreve um procedimento que calcula q e r, e esse procedimento é um algoritmo.

O resto pode ser negativo?

Na divisão euclidiana, não. Algumas linguagens de programação devolvem resto negativo, mas isso é uma convenção da linguagem, não da matemática.

O que acontece se o divisor for zero?

A divisão não está definida. O teorema exige b ≠ 0, e em programação isso gera erro ou exceção.

Onde o algoritmo da divisão é usado no dia a dia?

Em cálculos de horário, calendário, conversão para binário, criptografia e validação de dígitos verificadores, entre outros.

O que levar dessa leitura

O algoritmo da divisão formaliza a conta de dividir: quociente e resto existem e são únicos quando o resto fica entre zero e o divisor. Entender essa regra evita erros com números negativos no código e abre caminho para MDC, aritmética modular e criptografia.