FATOS MATEMÁTICOS: 2011/07

quarta-feira, 20 de julho de 2011

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.

Páginas

Membros

quarta-feira, 20 de julho de 2011

Teste de Primalidade