A divisão euclidiana, ou divisão com resto, é uma das quatro operações que toda criança aprende na escola. Sua formulação precisa é: dados , existem com e a = bq + r. Tais q e r estão unicamente determinados e são chamados o quociente e resto da divisão de a por b. Se b > 0 podemos definir e se b < 0, ; em qualquer caso, r = a - bq. O resto r é às vezes denotado por ; definimos . Lembramos que denota o único inteiro k tal que e o único inteiro k tal que .
Dados dois inteiros a e b (em geral com ) dizemos que b divide a, ou que a é um múltiplo de b, e escrevemos b | a, se existir com a = qb. Se , também dizemos que b é um divisor de a. Assim, b | a se e somente se .
Proposição 1.1: Dados existe um único tal que d|a, d|b e, para todo , se c|a e c|b então c|d. Além disso existem com d = ax + by.
Esse natural d é chamado o máximo divisor comum, ou mdc, entre a e b. Escrevemos ou (se não houver possibilidade de confusão) d = (a,b).
Dem: O caso a = b = 0 é trivial (temos d = 0). Nos outros casos, seja e seja d = a x0 + b y0 o menor elemento positivo de I(a,b). Como , existem com a = dq + r e . Temos ; como r < d e d é o menor elemento positivo de I(a,b), r = 0 e d | a. Analogamente, d | b. Suponha agora que c|a e c|b; temos c | a x + b y para quaisquer valores de x e ydonde, em particular, c|d.
O algoritmo de Euclides para calcular o mdc baseia-se nas seguintes observações simples. Se a = bq + r, , temos (com a notação da demonstração acima) I(a,b) = I(b,r), donde (a,b) = (b,r). Definindo a0 = a, a1 = b e an = an+1 qn+2 + an+2, (ou seja, an+2 é o resto da divisão de an por an+1) temos para qualquer valor de n. Seja N o menor natural para o qual aN+1 = 0: temos (a,b) = (aN,0) = aN.
Lema 1.2: Se (a, b) = 1 e a|bc então a|c.
Dem: Como (a, b) = 1, existem com ax + by = 1, logo a | c = acx + bcy.
Quando (a,b) = 1 dizemos que a e b são primos entre si. Um natural p > 1 é chamado primo se os únicos divisores positivos de p são 1 e p. Um natural n > 1 é chamado composto se admite outros divisores além de 1 e n.
Claramente, se p é primo e temos (p,a) = 1. Usando o lema anterior e indução temos o seguinte resultado:
Corolário 1.3: Sejam p um número primo e sejam . Se então p|ai para algum i, .
Estamos agora prontos para enunciar e provar o teorema que diz que todo inteiro admite fatoração única como produto de primos.
Teorema 1.4: (Teorema fundamental da aritmética)
Seja
um número natural.
Podemos escrever n de uma única forma como um produto
Dem: Mostramos a existencia da fatoração por indução. Se n é primo não há o que provar (escrevemos m = 1, p1 = n). Se n é composto podemos escrever n = ab, , 1 < a < n, 1 < b < n. Por hipótese de indução, a e b se decompõem como produto de primos. Juntando as fatorações de a e b(e reordenando os fatores) obtemos uma fatoração de n.
Vamos agora mostrar a unicidade, também por indução.
Suponha que
Outra forma de escrever a fatoração é
Segue deste teorema o outro algoritmo comum para calcular o mdc de dois números: fatoramos os dois números e tomamos os fatores comuns com os menores expoentes. Este algoritmo é bem menos eficiente do que o de Euclides para inteiros grandes (que em geral não sabemos fatorar) mas é instrutivo saber que os dois algoritmos dão o mesmo resultado.
Corolário 1.5: Se (a,n) = (b,n) = 1 então (ab,n) = 1.
Dem: Evidente a partir do algoritmo descrito acima.
Teorema 1.6: (Euclides) Existem infinitos números primos.
Dem: Suponha por absurdo que p1, p2,..., pm fossem todos os primos. O número não seria divisível por nenhum primo, o que contradiz o teorema fundamental da aritmética.
Observe que não provamos que é primo para algum conjunto finito de primos (por exemplo, os m primeiros primos). Aliás, , , 4! + 1 = 25 = 52 e não são primos. Não existe nenhuma fórmula simples conhecida que gere sempre números primos. Veja a seção 3.1.