Sejam a e b dois números inteiros. Dizemos que a divide b (ou que b é divisível por a) se existe um k inteiro tal que b = ak. Caso não exista tal inteiro, dizemos que a não divide b. Dizemos também que b é um múltiplo de a.
Naturalmente, qualquer número a divide a si mesmo (pois a = a x 1) e 1 divide qualquer número m (pois m = 1 x m). Veja que, segundo a definição acima, zero divide zero, pois 0 = k x 0 para qualquer k inteiro.
Agora, observe que, se a é diferente de zero e a divide b, então o inteiro k tal que b = ak é único: suponha que b = ak = at. Como a é diferente de zero, vale o cancelamento da multiplicação, de modo que k = t. O mesmo não acontece com zero: se s != r, ainda assim temos 0 = 0 x r = 0 x s. De fato, qualquer inteiro vezes zero é zero. Por isso o k não fica determinado (por isso que 0/0 é uma indeterminação). Para todos os demais valores a != 0, podemos definir o quociente k de b por a o inteiro k tal que b = ak.
A relação de divisibilidade a|b (a divide b) tem uma série de propriedades:
- a|0;
- se a|b e b|c então a|c (propriedade transitiva);
- a|a (propriedade reflexiva);
- se a|b e b|a, então a = +- b;
- se a|b então |a| <= |b|;
- se a|b e a|c então a|(bx + cy), para quaisquer x,y inteiros.
Sejam a,b inteiros, com b != 0. A Divisão de Euclides nos diz que existem únicos inteiros q,r, com 0 <= r < |b|, tais que a = bq + r. O número q é o quociente da divisão, e r é o resto.
A divisão euclidiana não é uma divisão de menor resto, o que pode levar a alguma dúvida quando
utilizado o operador % da linguagem C/C++. Por exemplo, veja o código abaixo:
#include <iostream>
int main()
{
int a = 11;
int b = 7;
std::cout << (a % b) << '\n'; // 4
std::cout << (a % -b) << '\n'; // 4
std::cout << (-a % b) << '\n'; // -4
std::cout << (-a % -b) << '\n'; // -4
return 0;
}Segundo a divisão euclidiana, teríamos:
11 = 7 x 1 + 4 // q = 1, r = 4
11 = (-7) x (-1) + 4 // q = 1, r = 4
-11 = 7 x (-2) + 3 // q = 1, r = 3
-11 = (-7) x 2 + 3 // q = 1, r = 3
Observe que, nos casos em que a < 0, o operador % retorna um resto negativo, o que viola a
condição 0 <= r < |b| da divisão de Euclides. Para determinar o resto euclidiano nestes casos,
basta somar b ao resto negativo.
Importante notar também que, se r == 0, então b divide a.
Dados dois inteiros a e b, o maior divisor comum (MDC) de a e b (notamos d = (a, b) é o inteiro não-negativo d tal que
- d divide a e d divide b;
- se c divide a e c divide b, então c divide d.
A pŕimeira condição apresentada garante que d é divisor comum; já a segunda garante que ele é o maior dentre os divisores comuns de a e b. Da definição pode-se observar que
- d == 0 se, e somente se, a = b = 0;
- (a, 0) = |a|, para todo inteiro a.
Como (a, b) = (-a, b) = (a, -b) = (-a,-b), podemos restringir o problema de se determinar o MDC aos números não-negativos.
Sejam a e b dois inteiros não-negativos, com b != 0. A divisão de Euclides garante a existência de inteiros q e r tais que a = bq + r, com 0 <= r < b. Escrevendo r = a - bq, é possível mostrar que (a, b) = (b, r). Este resultado, atribuído a Euclides, juntamente com o caso base apresentado anteriormente, nos permite implementar o cálculo do MDC de maneira eficiente e sintética.
long long gcd(long long a, long long b)
{
return b ? gcd(b, a % b) : a;
}Também é possível mostrar que o MDC entre a é b é o menor número não-negativo que pode ser escrito como uma combinação ax + by. Esta interpretação é fundamental para a demonstração de várias propriedades associadas ao MDC. Para se determinar tais inteiros x e y (os quais não são únicos), podemos usar uma versão estendida do algoritmo do MDC, mostrada abaixo.
long long ext_gcd(long long a, long long b, long long& x, long long& y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
long long x1, y1;
long long d = ext_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1*(a/b);
return d;
}Uma importante aplicação do MDC e do algoritmo de Euclides estendido é a solução de Equações Diofantinas Lineares, isto é, equações da forma ax + by = c, com a, b, c, x, y inteiros. Tais equações tem solução se, e somente se, (a, b) divide c. Se isto acontecer, procedemos da seguinte maneira
- usando o algoritmo estendido de Euclides, determinamos x1 e y1 tais que ax1 + by1 = d
- Faça k = c / d
- Multiplicando a equação do passo 1 por k, obtemos x0 = k x x1 e y0 = k * y1, e ax0 + by0 = d * k = c.
A solução encontrada acima não é única: o conjunto completo das soluções da equação diofantina é dado por x = x0 + at, y = y0 - bt, para qualquer t inteiro. Estas expressões nos permitem determinar, por exemplo, soluções específicas, como a de menor x (ou y), menor diferença entre x e y, menor solução com x e y positivos, e assim por diante (se existirem).
Dois números a e b são dito coprimos se (a, b) = 1. Observe que, para dois inteiros a e b quaisquer, se d = (a, b), então (a/d, b/d) = 1.
Sejam a e b dois inteiros. O menor múltiplo comum (MMC) de a e b (notamos m = [a,b]) é o inteiro m tal que
- a divide m e b divide m;
- se a divide n e b divide n, então m divide n.
De forma similar ao MDC, a primeira propriedade torna m um múltiplo comum de a e b; já a segundo o torna o menor dentre os múltiplos comuns.
Uma importante relação entre o MDC e o MMC é que ab = (a,b)[a,b]. Esta relação nos permite computar o MMC entre dois números de forma direta, uma vez conhecido o MDC.
long long lcm(long long a, long long b)
{
return (a/gcd(a, b))*b;
}Veja que, na implementação acima, a divisão é feita antes do produto: esta ordem pode evitar overflow em alguns casos.
HEFEZ, Abramo. Aritmética.