Justificando o algoritmo
Nesta sala, vamos obter respostas para as três perguntas formuladas na Sala Principal sobre o Algoritmo de Fermat:
2) Nos casos em que [tex]n[/tex] for um inteiro composto ímpar, maior do que [tex]1[/tex], e não for um quadrado perfeito, sempre encontraremos um valor para [tex]x[/tex], com [tex][\sqrt{n}]+1\le x \lt \dfrac{n+1}{2}[/tex], tal que [tex]y=\sqrt{x^2-n}[/tex] seja inteiro e [tex]x-y[/tex] seja maior que [tex]1[/tex]?
3) Podemos ter certeza de que [tex]n[/tex] é primo se [tex]x[/tex] chegar a [tex]\dfrac{n+1}{2}[/tex]?
Já observamos que, respondendo afirmativamente às perguntas 2 e 3, responderemos à pergunta 1 e garantiremos que o processo descrito é realmente um algoritmo, pois ele tem fim. Mais do que isso, observe que o sim das respostas às perguntas 2 e 3 mostram a eficiência desse algoritmo, já que o primeiro passo é executado apenas uma vez e garante a fatoração para quadrados perfeitos.
Assim, como já sabemos que essas duas repostas são SIM, vale a pena conhecermos suas justificativas.
Primeiramente vamos nos ater à pergunta [tex]2[/tex]. Observamos que a resposta SIM a ela, além de indicar que o processo tem um fim quando [tex]n[/tex] é composto, indica que ele é útil, pois poderemos escrever [tex]n[/tex] na forma [tex](x-y)(x+y)[/tex] com [tex]x-y\gt1[/tex] (e, consequentemente, [tex]1\lt x+y\lt n[/tex]), ou seja, fatoraremos [tex]n[/tex] de uma forma diferente da forma trivial [tex]n=1\cdot n[/tex].
Dado [tex]n[/tex], um inteiro composto ímpar maior do que [tex]1[/tex] e que não seja um quadrado perfeito, seja [tex]n=a\cdot b[/tex] uma fatoração para [tex]n[/tex], com [tex]a[/tex] e [tex]b[/tex] inteiros tais que [tex]1\lt a\lt b\lt n[/tex]. Estamos supondo [tex]a\not = b[/tex], pois [tex]n[/tex] não é um quadrado perfeito. Como [tex]n[/tex] é ímpar, observe que [tex]a[/tex] e [tex]b[/tex] devem ser ímpares também.
Precisamos assegurar a existência de números inteiros positivos [tex]x[/tex] e [tex]y[/tex] tais que tais que [tex]n=x^2-y^2[/tex]. Que números seriam estes?
Observe que, nessas condições, por um lado temos [tex]n=a\cdot b[/tex] e, por outro, teríamos [tex]n=x^2-y^2[/tex], assim:
[tex]\qquad \qquad a\cdot b=n=(x-y)\cdot (x+y)[/tex].
A igualdade [tex] a\cdot b= (x-y)\cdot (x+y)[/tex] nos sugere que [tex] a=x-y[/tex] e [tex] b= x+y[/tex] e, dessa forma, teríamos dois candidatos a [tex]x[/tex] e [tex]y[/tex]:
[tex]\qquad \qquad \boxed{x=\dfrac{a+b}{2}} \, \, [/tex] e [tex] \, \, \boxed{y=\dfrac{b-a}{2}}[/tex].
Bom, já temos os candidatos; a pergunta agora é essa: esses valores satisfazem todas as condições que devem ser satisfeitas?
Vejamos…
(i) Como [tex]1\lt a\lt b\lt n[/tex], então [tex]a+b \gt 0[/tex] e [tex]b-a \gt 0[/tex].
Logo, [tex]x[/tex] e [tex]y[/tex] são positivos.
(ii) Como [tex]a[/tex] e [tex]b[/tex] são ímpares, então [tex]a+b[/tex] e [tex]b-a[/tex] são pares. Assim, [tex]x[/tex] e [tex]y[/tex] são inteiros.
(iii) Observe que
[tex]\qquad \qquad x^2-y^2=\left(\dfrac{a+b}{2}\right)^2-\left(\dfrac{b-a}{2}\right)^2=a\cdot b=n[/tex],
ou seja, [tex]n=x^2-y^2[/tex], donde [tex]y=\sqrt{x^2-n}[/tex], já que [tex]y[/tex] é positivo.
(iv) Sabemos que [tex](\sqrt{a}-\sqrt{b})^2\gt 0[/tex]; assim [tex]a-2\sqrt{a\cdot b}+b\gt 0[/tex] e, então, [tex]\sqrt{a\cdot b}\lt\dfrac{a+b}{2}[/tex].
Dessa forma, [tex]\sqrt{n} \lt x[/tex] e, portanto, a parte inteira de [tex]x[/tex] é maior do que a parte inteira de [tex]\sqrt{n}[/tex]. Como [tex]x[/tex] é inteiro, então [tex]x \gt [\sqrt{n}][/tex].
Mas [tex][\sqrt{n}] \lt [\sqrt{n}]+1[/tex], logo [tex][\sqrt{n}]+1 \le x[/tex].
(v) Sendo [tex]b\gt a\ge 2[/tex], temos [tex]2\lt b[/tex], portanto [tex]a=\dfrac{a}{2}\cdot2 \lt\dfrac{a}{2}\cdot b=\dfrac{a\cdot b}{2}[/tex] e, assim, [tex]a\lt \dfrac{a\cdot b}{2}[/tex].
Por outro lado, de [tex]2\le a [/tex], segue que [tex] b=2\cdot\dfrac{b}{2}\le a\cdot \dfrac{ b}{2}=\dfrac{a\cdot b}{2}[/tex], ou seja, [tex] b \le \dfrac{a\cdot b}{2}[/tex].
De [tex]a\lt \dfrac{a\cdot b}{2} \, [/tex] e [tex] \, b\le \dfrac{a\cdot b}{2}[/tex], vem que
[tex]a+b\lt \dfrac{a\cdot b}{2}+\dfrac{a\cdot b}{2}=\dfrac{a\cdot b+a\cdot b}{2}=a\cdot b\lt a\cdot b+1[/tex]
e, dividindo por [tex]2[/tex], temos
[tex]\dfrac{a+b}{2}\lt\dfrac{a\cdot b+1}{2}=\dfrac{n+1}{2}[/tex].
Portanto, [tex]x \lt \dfrac{n+1}{2}[/tex].
(vi) Note que [tex]x-y=\dfrac{a+b-b+a}{2}=\dfrac{2a}{2}=a\gt1[/tex].
Assim, [tex]x-y \gt 1[/tex].
Com tudo isso, provamos que se [tex]n[/tex] é um inteiro composto ímpar maior do que [tex]1[/tex] e que não seja um quadrado perfeito, então há pelo menos um [tex]x[/tex] e um [tex]y[/tex], inteiros positivos, a saber, [tex]x=\dfrac{a+b}{2} \, [/tex] e [tex] \, y=\dfrac{b-a}{2}[/tex], com [tex][\sqrt{n}]+1\le x\lt\dfrac{n+1}{2}[/tex], [tex]x-y\gt1[/tex], de modo que [tex]n=x^2-y^2 [/tex].
Assegurado, então, que o algoritmo funciona para [tex]n[/tex] composto e não quadrado perfeito, a pergunta [tex]2[/tex] está respondida afirmativamente.
A resposta à pergunta [tex]3[/tex] é mais simples.
Note também que [tex]x=\dfrac{n+1}{2}[/tex] é o único valor válido para [tex]x[/tex] se [tex]n[/tex] é primo.
De fato, no caso em que [tex]n[/tex] é primo, a decomposição trivial [tex]n=1\cdot n[/tex] é a única possível. Neste caso, se [tex]n[/tex] for escrito na forma [tex]n=x^2-y^2[/tex], devemos ter [tex]x-y=1[/tex] e [tex]x+y=n[/tex].
Resolvendo este sistema de duas equações a duas incógnitas, encontramos [tex]x=\dfrac{n+1}{2}[/tex] e [tex]y=\dfrac{n-1}{2}[/tex].
Assegurado, agora, que o algoritmo funciona para [tex]n[/tex] primo, a pergunta [tex]3[/tex] está também respondida afirmativamente.