Vamos começar enunciando o Lema de Thue, prová-lo, e em seguida apresentar problemas resolvidos e propostos para o leitor.
Lema de Thue: Seja $$n>1$$ um inteiro e $$a$$ um inteiro tal que $$mdc(a,n)=1$$. Então existem $$x,y$$ tais que $$0<|x|,|y|\le \lfloor\sqrt{n}\rfloor$$ e
$$ax\equiv y\:(mod\:n)$$
Prova: Tome primeiro o caso em que $$n$$ não é quadrado perfeito. Considere todos os pares ordenados de inteiros $$(x,y)$$ com ambas as variáveis entre $$0$$ e $$\lfloor\sqrt{n}\rfloor$$. Logo, há $$(\lfloor\sqrt n\rfloor+1)^2=\lfloor\sqrt n\rfloor^2+2\cdot\lfloor\sqrt n\rfloor+1>(\sqrt n-1)^2+2(\sqrt n-1)+1=n-2\sqrt n+1+2\sqrt n-2+1=n$$ pares, ou seja, há pelo menos $$n+1$$ pares $$(x,y)$$, e como a expressão $$ax-y$$ só pode assumir $$n$$ valores módulo $$n$$, segue por PCP que existem dois pares diferentes $$(x_1,y_1)$$ e $$(x_2,y_2)$$ tais que $$ax_1-y_1\equiv ax_2-y_2\:(mod\:n) \iff a(x_1-x_2)\equiv (y_1-y_2)\:(mod\:n)$$. Mas note que, como $$a$$ e $$n$$ são primos entre si, $$x_1=x_2 \iff y_1=y_2$$,, e qualquer das igualdades geraria igualdade dos pares, um absurdo, e logo $$|x_1-x_2|,|y_1-y_2|>0$$. Por outro lado, $$|x_1-x_2|\le max\{x_1,x_2\}\le \lfloor\sqrt{n}\rfloor$$ e $$|y_1-y_2|\le max\{x_1,x_2\}\le \lfloor\sqrt{n}\rfloor$$, e tomando $$x=x_1-x_2$$ e $$y=y_1-y_2$$ segue o que queríamos.
Há também o:
Lema de Thue generalizado: Sejam $$\alpha$$ e $$\beta$$ dois números reais positivos tais que $$\alpha\beta\ge p$$. Então para um inteiro $$a$$ coprimo com $$p$$, existem $$x,y$$ inteiros tais que $$0<x\le\alpha$$, $$0<y\le\beta$$ e
$$ax\equiv y\:(mod\:p)$$
A prova é análoga e deixada como exercício.
Vamos aos exemplos resolvidos!
Exemplo 1: Seja $$p$$ um primo para o qual existe um inteiro positivo $$a$$ tal que $$p$$ divide $$2a^2-1$$. Prove que existem inteiros $$b$$ e $$c$$ de modo que $$p=2b^2-c^2$$
Solução: Pelo Lema de Thue, como $$a$$ é coprimo com $$p$$, tome $$b,c$$ inteiros tais que $$0<|b|,|c|<\sqrt{p}$$ e $$ca\equiv b\:(mod\:p)$$. Veja que pela limitação de $$b$$ e $$c$$, ambos são primos com $$p$$ e portanto invertíveis módulo $$p$$. Logo,$$2a^2-1\equiv 0 \:(mod\:p)\iff 2(b\cdot c^{-1})^2-1\equiv 0\:(mod\:p) \iff 2b^2-c^2\equiv 0\:(mod\:p)$$. Agora, note que $$2b^2-c^2>-c^2>-(\sqrt{p})^2=-p$$ e $$2b^2-c^2<2b^2<2p$$ e como $$p|2b^2-c^2$$, há duas possibilidades: $$2b^2-c^2=0\Rightarrow \sqrt 2=\dfrac{c}{b}\Rightarrow \sqrt2$$ é racional, um absurdo, ou $$2b^2-c^2=p$$, que é a única que pode ocorrer, demonstrando a existência de $$b$$ e $$c$$ nas condições do enunciado que queríamos.
Exemplo 2: Se $$p$$ é um primo da forma $$3k+1$$, então existem inteiros $$a$$ e $$b$$ tais que $$p=a^2+ab+b^2$$
Solução: Inicialmente, vamos provar que $$-3$$ é resíduo quadrático módulo $$p$$. Note que $$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)$$, mas pela Lei da Reciprocidade Quadrática temos que $$\left(\frac{3}{p}\right)=(-1)^{\frac{p-1}{2}\frac{3-1}{2}}\cdot \left(\frac{p}{3}\right) $$, e pelo Critério de Euler $$\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$$, portanto: $$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)=\left(\frac{-1}{p}\right)(-1)^{\frac{p-1}{2}\frac{3-1}{2}}\left(\frac{p}{3}\right)=(-1)^{p-1}\left(\frac{1}{p}\right)=1$$ e segue o que foi afirmado. Seja agora $$m$$ tal que $$m^2\equiv-3\:(mod\:p)$$. Como $$p$$ é ímpar, $$2$$ é invertível, e tome $$x\equiv (m-1)\cdot 2^{-1}\:(mod\:p)\Rightarrow (2x+1)^2\equiv -3\:(mod\:p)\Rightarrow 4x^2+4x+4\equiv 0\:(mod \:p)\Rightarrow x^2+x+1\equiv 0\:(mod\:p)$$.
Pelo Lema de Thue, como $$x$$ é coprimo com $$p$$, tome $$0<|a|,|b|<\sqrt{p}$$ tais que $$ax\equiv b\:(mod\:p) \iff x\equiv b\cdot a^{-1} \:(mod\:p)$$. Então podemos substituir o valor de $$x$$ e obter $$x^2+x+1\equiv 0\:(mod\:p)\Rightarrow (b\cdot a^{-1})^2+b\cdot a^{-1}+1\equiv 0\:(mod\:p)\iff a^2+ab+b^2\equiv 0\:(mod\:p) $$. Agora, veja que $$a^2+ab+b^2>0$$ pois, de fato, se $$ab>0$$ o resultado é claro, e se $$ab<0$$, $$a^2+ab+b^2>a^2+2ab+b^2=(a+b)^2>0$$. Por outro lado, pela limitação de $$a,b$$ do Lema de Thue, sabe-se que $$a^2+ab+b^2<3(\sqrt{p})^2=3p$$ e como $$p|a^2+ab+b^2$$, essa expressão só pode assumir os valores $$p$$ e $$2p$$. Mas se tivéssemos $$a^2+ab+b^2=2p\Rightarrow a^2+ab+b^2\equiv 2\:(mod\:3)$$. Se $$a\equiv0$$, $$b^2\equiv2$$, um absurdo. Se $$a\equiv1$$, $$b^2+b\equiv1$$, um absurdo pois $$x^2+x\equiv 0,2,0$$ ao fazermos $$x=0,1,2$$. Logo, $$a\equiv 2\Rightarrow b^2+2b\equiv 1$$, também absurdo pois $$x^2+2x\equiv 0,0,2$$ com $$x=0,1,2$$. Finalmente, só há uma possibilidade, que é $$a^2+ab+b^2=p$$, como queríamos.
Teorema: Um número inteiro $$n$$ pode ser escrito como soma de dois quadrados perfeitos se,e somente se, sua fatoração em primos não contém nenhum primo da forma $$4k+3$$ com expoente ímpar.
Prova: Comecemos pelo seguinte:
Lema 1: Se $$p$$ é um primo da forma $$4k+3$$ e $$p|x^2+y^2$$ então $$p|x$$ e $$p|y$$, donde $$p^2|x^2+y^2$$.
Prova: $$p|x^2+y^2 \iff x^2\equiv -y^2\:(mod\:p) \iff (x^2)^{\frac{p-1}{2}}\equiv(-y^2)^{\frac{p-1}{2}}\:(mod\:p)$$, mas pelo Pequeno Teorema de Fermat, supondo que $$p$$ não divide $$x$$ nem $$y$$, vale que $$x^{p-1}\equiv y^{p-1}\equiv 1\:(mod\:p)$$ e logo $$(-1)^{\frac{p-1}{2}}\equiv 1\:(mod\:) \iff (-1)^{2k+1}\equiv 1 \:(mod\:p) \iff -1\equiv 1\:(mod\:p)$$, um absurdo. Logo, $$p$$ divide um dentre $$x$$ e $$y$$ e logo divide o outro, e segue $$p|x$$ e $$p|y$$.
Lema 2: Se $$p$$ é um primo da forma $$4k+1$$, então ele pode ser escrito como soma de quadrados.
Prova: Pelo critério de Euler, $$\left(\dfrac{-1}{p}\right)\equiv (-1)^{\frac{p-1}{2}}=(-1)^{2k}=1\:(mod\:p)\Rightarrow$$ $$-1$$ é resíduo quadrático módulo $$p$$, ou seja, existe $$x$$ tal que $$x^2\equiv-1$$. Tome, pelo Lema de Thue, já que $$mdc(x,p)=1$$, existem inteiros $$a,b$$ tais que $$0<|a|,|b|<\sqrt p$$ e $$ax\equiv b\:(mod\:p)$$. Então $$x\equiv b\cdot a^{-1} \:(mod\:p)\iff (b\cdot a^{-1})^2\equiv -1\:(mod\:p) \iff b^2\equiv -a^2 \:(mod\:p) \iff p|a^2+b^2$$, e como nós sabemos que $$0<a^2+b^2<2(\sqrt{p})^2=2p$$, segue que a única possibilidade é $$a^2+b^2=p$$.
Agora, veja que se dois números podem ser escritos como soma de quadrados, então seu produto também pode, pois: $$(d^2+e^2)(f^2+g^2)=(df)^2+2defg+(eg)^2+(dg)^2-2defg+(ef)^2=(df+eg)^2+(dg-ef)^2$$, logo, como $$2=1^2+1^2$$ e todo primo da forma $$4k+1$$ é escrito como soma de dois quadrados pelo Lema 2, basta que o número tenha expoentes pares nos primos da forma $$4k+3$$, de modo que possamos os escrever como $$q^2=q^2+0^2$$ e utilizar a propriedade citada acima. Além disso, se $$p=4k+3$$ é um primo que divide $$n=a^2+b^2$$ então pelo Lema 1 vale que $$p|a$$ e $$p|b$$, donde $$\dfrac{n}{p^2}=\left(\dfrac{a}{p}\right)^2+\left(\dfrac{b}{p}\right)^2$$. Se $$p$$ ainda divide $$\dfrac{n}{p^2}$$, podemos realizar raciocínio análogo, e ir retirando duas unidades do expoente de $$p$$ em $$n$$. Caso esse fosse ímpar, em algum momento do algoritmo teríamos o $$p$$ com expoente $$1$$, e pelo lema 1 seguiria um absurdo. Logo, a condição dos expoentes dos fatores primos da forma $$4k+3$$ de um número serem pares é necessária e suficiente para que ele seja escrito como soma de quadrados, como queríamos.
Problemas Propostos:
Problema 1: Seja $$a$$ um inteiro positivo e $$p$$ um divisor primo de $$a^3-3a+1$$, com $$p\neq3$$. Prove que $$p$$ é da forma $$9k+1$$ ou $$9k-1$$, onde $$k$$ é um inteiro.
Obs: A solução desse problema pode ser encontrada em OBM-2017-P6.
Problema 2: Seja $$p$$ um número primo. Prove que existem inteiros $$x,y$$ tais que $$p=2x^2+3y^2$$ se, e somente se, $$p\equiv 5,11\:(mod\:24)$$.
Problema 3: Seja $$S$$ o conjunto de todos os inteiros positivos que podem ser repreentados como $$a^2+5b^2$$ para inteiros $$a,b$$ tais que $$mdc(a,b)=1$$. Seja $$p$$ um número primo tal que $$p=4n+3$$ para algum inteiro positivo $$n$$. Mostre que se para algum inteiro positivo $$k$$ o número $$kp$$ pertence à $$S$$, então $$2p$$ também está em $$S$$.
Problema 4: Prove que a equação $$x^3-x+9=5y^2$$ não tem solução nos inteiros.