Teoria dos Números
Teoria dos números é um ramo da matemática que estuda números inteiros. Nessa seção, assumiremos que todos os números são inteiros.
Divisores
Um número \(a\) é chamado de divisor ou fator de um número \(b\) se \(a\) divide \(b\). Escrevemos \(a \mid b\) e temos a seguinte propriedade:
Por exemplo, os divisores de \(24\) são \(1, 2, 3, 4, 6, 8, 12\) e \(24\).
Primos
Um número \(n > 1\) é primo se seus únicos divisores positivos são \(1\) e \(n\). Por exemplo, \(7, 19\) e \(41\) são primos, mas 35 não é primo pois \(5 \cdot 7 = 35\). Para todo número \(n > 1\) existe uma única fatoração em primos:
Em que \(p_1, p_2, ..., p_k\) são primos distintos e \(\alpha_1, \alpha_2, \cdots, \alpha_k\) são inteiros positivos. Por exemplo, a fatoração do número 84 é:
Número de divisores
O número de divisores de um número \(n\) é:
Porque para todo primo \(p_i,\) existem \(\alpha_i + 1\) formas de escolher quantas vezes ele aparece no divisor, de \(p_i^0\) até \(p_i^{\alpha_i}\). Por exemplo, o número de divisores de 84 é:
Soma dos divisores
A soma dos fatores de \(n\) é:
Pois podemos escolher qualquer potência dos primos presentes na fatoração de \(n\), de \(p_i^{0} = 1\) até \(p_i^{\alpha_i}\). A simplificação pode ser feita pela soma de progressão geométrica com razão \(p_i\):
Por exemplo, a soma dos fatores de 84 é:
Produto dos divisores
O produto dos divisores de \(n\) é:
Porque podemos formar \(\tau(n)/2\) pares de divisores, cada um com produto igual à \(n\). Por exemplo, os doze fatores de \(84\) produzem seis pares:
e o produto dos fatores é \(\mu(84) = 84^{6} = 351298031616\).
Densidade de primos
A densidade de números primos \(\pi(n)\) representa a quantidade de primos entre \(1\) e \(n\). Temos a aproximação:
Por exemplo \(\pi(10) = 4,\) pois temos \(4\) primos entre \(1\) e \(10:\) \(2, 3, 5, 7\).
Algoritmos básicos
Se um número \(n\) não é primo, ele pode ser representado como um produto \(a \cdot b,\) em que \(a \leq \sqrt{n}\) ou \(b \leq \sqrt{n}\), portanto existe um fator entre \(2\) e \(\lfloor\sqrt{n}\rfloor\). Assim, podemos testar se um número é primo e achar sua fatoração em \(O(\sqrt{n})\).
Identificar se um número é primo
A função \(is \_ prime\) abaixo checa se o número \(n\) é primo. Sabemos que o único número par primo é \(2\), portanto podemos checar a paridade de \(n\) e tentar dividir \(n\) apenas pelos números impares entre \(3\) e \(\lfloor \sqrt{n} \rfloor\).
is_prime.cpp | |
---|---|
Fatorar um número
A função \(factor\) abaixo retorna um vetor que contém a fatoração em primos do número \(n\). A função divide \(n\) pelos seus divisores primos e os adiciona no vector. O processo encerra quando \(n\) não tem mais fatores entre \(2\) e \(\lfloor \sqrt{n} \rfloor\). Ao final do processo, se \(n > 1\), ele é primo e é o último divisor.
factor.cpp | |
---|---|
Crivo de Eratóstenes
O crivo de Eratóstenes é um algoritmo que constrói um vetor no qual podemos usar de maneira eficiente para determinar se um determinado número entre \(0\) e \(n\) é primo. O algoritmo constrói um vetor \(prime\) cujas posições \(0, 1, 2, 3, \cdots, n\) são usadas. O valor \(prime[k] = 1\) significa que \(k\) é primo, e o valor \(prime[k] = 0\) significa que \(k\) não é primo.
O algoritmo itera sobre os números \(2, \cdots, n\) um por um. Sempre que um novo primo \(x\) é encontrado, o algoritmo guarda que os múltiplos de \(x\) \((2x, 3x, 4x, \cdots)\) não são primos, pois são divisíveis por x.
crivo.cpp | |
---|---|
O loop interior do algoritmo é executado \(n/x\) vezes para cada valor de \(x\). Portanto, um upper bound para a complexidade de tempo é a série harmônica
Na realidade, o algoritmo é mais eficiente, pois o loop interior vai ser executado apenas se o número \(x\) é primo, cuja frequência é aproximadamente \(\frac{n}{\ln(n)}\). Portanto, a complexidade de tempo do algoritmo é \(O(n \log \log n)\), sendo muito próxima de \(O(n)\).
Podemos alterar o algoritmo para obter a fatoração de cada número entre \(2\) e \(n\), criando um novo vetor \(d\) de vectors, em que \(d[k]\) guarda a fatoração em primos do número \(k\).
crivo_div.cpp | |
---|---|
Máximo Divisor Comum (MDC ou GCD)
O máximo divisor comum de dois números \(a\) e \(b\), \(\gcd(a,b)\), é o maior número que divide tanto \(a\) quanto \(b\). Por exemplo, \(\gcd(24,36) = 12\).
Algoritmo de Euclides
O algoritmo de euclides é uma maneira eficiente de calcular o \(\gcd\) de dois números. Ele é baseado na seguinte fórmula:
O algoritmo de Euclides funciona em tempo \(O(\log n)\), em que \(n = \min(a,b)\).
O pior caso acontece quando \(a\) e \(b\) são números consecutivos de Fibonacci. Por exemplo,
Mínimo múltiplo comum (MMC ou LCM)
O mínimo múltiplo comum de dois números \(a\) e \(b\), \(lcm(a,b)\), é o menor número que é divisível por \(a\) e por \(b\). Por exemplo, \(lcm(24,36) = 72.\)
O \(\gcd\) e o \(lcm\) possuem a seguinte propriedade:
Função totiente de Euler
Números \(a\) e \(b\) são coprimos se \(\gcd(a,b) = 1\). A função totiente de Euler \(\varphi(n)\) calcula a quantidade de números coprimos com \(n\) entre \(1\) e \(n\). Por exemplo, \(\varphi(12) = 4\), porque \(1, 5, 7\) e \(11\) são coprimos com \(12\).
O valor de \(\varphi(n)\) pode ser calculado pela fatoração em primos de \(n\) usando a formula:
Por exemplo, \(\varphi(12) = (2^1 \cdot (2-1)) \cdot (3^0 \cdot (3-1)) = 4\).
Note que \(\varphi(n) = n-1\) se \(n\) é primo.
Aritmética modular
Na aritmética modular, o conjunto de números é limitado para apenas \(0, 1, 2, \cdots, m-1\), em que \(m\) é uma constante.
Cada número \(x\) é representado pelo número \(r\) tal que
Por exemplo, \(75 \bmod 17 = 7\).
Pode-se calcular o módulo antes de algumas operações para evitar números muito grandes. Algumas propriedades são:
Exponenciação Rápida
Existe um jeito de calcular o valor de \(x^n \bmod m\) em \(O(\log n)\) utilizando a seguinte recursão:
É importante que no caso de \(n\) ser par, o valor de \(x^{n/2}\) é calculado apenas uma vez. Isso garante a complexidade \(O(\log n)\), porque \(n\) é sempre dividido por dois quando é par.
fastexp.cpp | |
---|---|
Pequeno teorema de Fermat e teorema de Euler
Para um \(m\) primo e coprimo com \(x\), o pequeno teorema de Fermat afirma que
Pode-se expandir para
De forma geral, o teorema de Euler para \(x\) e \(m\) coprimos afirma que
O teorema de Fermat é equivalente ao teorema de Euler, pois \(\varphi (m) = m-1\) para \(m\) primo.
Inverso modular
O inverso de \(x \bmod m\) é um número \(x^{-1}\) tal que
Usando inversos modulares, é possível dividir números módulo \(m\), porque divisão por \(x\) corresponde à multiplicação por \(x^{-1}\).
No entanto, o inverso modular nem sempre existe. Por exemplo, se \(x = 2\) e \(m = 4\), a equação \(x \cdot x^{-1} \bmod m = 1\) não tem solução, porque todos os múltiplos de 2 serão pares e o resto nunca poderá ser \(1\) quando \(m = 4\). Temos que \(x^{-1} \bmod m\) pode ser calculado apenas quando \(x\) e \(m\) são coprimos.
Pelo teorema de Euler,
Portanto, por definição, os números \(x^{-1}\) e \(x^{\varphi(m)-1}\) são equivalentes módulo \(m\).
Se \(m\) é primo, obtemos
Essa fórmula permite calcular inversos modulares de uma forma eficiente utilizando o algoritmo da exponenciação rápida.
Por exemplo, \(6^{-1} \bmod 17 = 6^{17 - 2} \bmod 17 = 3\). Note que \(6 \cdot 3 \bmod 17 = 1\).