Membros

quarta-feira

Teste de Primalidade

Proposição 1: (Teste de Primalidade) Seja [;k;]um primo ímpar e [;x\;] um número ímpar qualquer. Se no intervalo [;2 \prec k \leq \sqrt{x};],

[;f(k,x) = \frac{x^2 + k^2}{2k};]
não for um inteiro, então [;x\;] é primo.

Demonstração: Sejam [;x,y;] e [;z;] números inteiros; se na equação [;x^2 + y^2 = z^2;]:

a) [;x\;] for ímpar composto, o número de soluções é igual ao número de divisores positivos de [;x^2;] menores que [;x\;];
b) [;x\;] for um primo ímpar, tem apenas uma solução.

a) A equação [;x^2 + y^2 = z^2;] pode ser escrita da seguinte forma:

[;z + y = \frac{x^2}{z - y} \qquad (1);]

Uma vez que [;z;] e [;y;] são inteiros, então [;z - y;] tem que dividir [;x^2;] sem deixar resto. Logo, [;z - y;] são os divisores positivos de [;x^2;].

Seja [;z - y = k;]. Substituindo esta expressão em [;(1);], obtemos o seguinte sistema de equações:

[;\begin{cases}z - y = k\\z+y = \frac{x^2}{k}\end{cases};]

Resolvendo o sistema de equações acima, obtém-se a seguinte solução:

[;2z = k + \frac{x^2}{k} \quad \Rightarrow \quad z = \frac{x^2 + k^2}{2k};]

Como [;z = y - k;], então, [;y = z - k;]. Se [;k = x;], então [;z = \frac{x^2 + x^2}{2x} = x;]. Como [;y = z - k;], então [;y = x - x = 0;]. Logo, [;k;] deve ser menor que [;x\;]. Portanto, se [;x\;] for um ímpar composto, o número de soluções é igual ao número de divisores de [;x^2;] menores que [;x\;], ou seja, [;k \prec x;] (fad).

b) Como [;x\;], [;y;] e [;z;] têm que ser inteiros, logo, pela equação [;(1);], [;z - y;] tem que dividir [;x^2;] sem deixar resto. Como [;x\;] é um primo ímpar, os divisores de [;x^2;], [;x\;] e [;1;]. Substituindo [;z - y;], na equação [;(1);], respectivamente, por [;x^2;], [;x\;] e [;1;], obtém-se os seguintes sistemas de equações:

[;S_1: \begin{cases}z - y = x^2\\z + y = 1\end{cases} \qquad \qquad S_2: \begin{cases}z - y = x\\z + y = z \end{cases}\qquad \qquad S_3: \begin{cases}z - y = 1\\z + y = x^2\end{cases};]

Dos três sistemas de equações acima, somente o [;S_3;] é compatível. Resolvendo-o, obtém-se:

[;z = \frac{x^2 + 1}{2} \quad \text{e} \quad y = z - 1 \quad (fad);]

Conclusão: Se [;k;] (ímpar) [;\succ 1;], a equação [;z = (x^2 + k^2)/(2k);], só terá [;z;] inteiro se [;x\;] for um ímpar composto. Portanto, se [;x\;] for um ímpar qualquer e [;k;] (ímpar) [;\succ 1;] um primo ímpar, [;z;] só será um inteiro se [;x\;] for um ímpar composto.

Em virtude de a função [;f(x,k);] existir [;\sqrt{x};], ela não é eficiente, em tempo computacional, para testar a primalidade de primos grandes, mas o que existe de curioso nela, é que ela gera todos os primos, e em sequência.

Exemplos: Como [;\sqrt{3};], [;\sqrt{5};] e [;\sqrt{7};] são menores que [;3;] e [;k;] deve ser um primo ímpar maior que [;2;], logo, o teste de primalidade começa com o primo [;11;].

Artigo enviado por Sebastião Vieira do Nascimento (Sebá). Professor Titular (por concurso) aposentado da UFCG - Universidade Federal de Campina Grande - PB.

Gostará de ler também:
- Teoremas Interessantes Sobre Números Primos;
- O Maior Número Primo Conhecido;
- Três Fórmulas no Sistema de Amortização Constante (SAC) que não Existem em Nenhum Livro de Matemática Financeira.