Matemática

Teste de Primalidade

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

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;]

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;]

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

. 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

, então,

. Se

, então $[;z = \frac{x^2 + x^2}{2x} = x;]$ . Como [;y = z - k;]

, então

. Logo,

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;]

têm que ser inteiros, logo, pela equação [;(1);]

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á

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;]

deve ser um primo ímpar maior que [;2;]

, logo, o teste de primalidade começa com o primo [;11;]

- Números Primos
Devemos antes de tudo lembrar o que são números primos. Definimos como números primos aqueles que são divisíveis apenas por 1 e ele mesmo. Um número seja maior do que 1 que não seja primo é chamado de composto. Exemplos: 2 tem apenas os divisores...

- NÚmeros Primos
Os números que admitem apenas dois divisores (ele próprio e 1 ) são chamados de números primos. exemplos a) 2 é um número primo, pois D2 = { 1,2} b) 3 é um número primo, pois D3 = { 1,3} c) 5 é um número primo, pois D5 = { 1,5} d) 7 é um número...

- O Tijolo De Euler
Por: Sebastião Vieira do Nascimento (Sebá) Este artigo é sobre aplicação de ternos pitagóricos em um dos problemas insolúveis da Matemática. O tijolo de Euler é um paralelepípedo regular de lados que são números inteiros $A$, $B$ e $C$, sendo...

- Como Construir Uma Espiral Pitagórica
A Espiral Pitagórica é construída com triângulos retângulos cujas medidas dos lados são expressas por números inteiros. Veremos neste post sua construção, assim como o desenvolvimento das fórmulas que geram os lados dos triângulos. A Espiral...

- Deserto Entre Números Primos
Por: Sebastião Vieira do Nascimento (Sebá) Dando continuação ao trabalho publicado neste blog sob o título: Construindo uma Sequencia de Números Não-primos, vamos mostrar, por meio de exemplos, que existem outros números não-primos (ou números...

Matemática