Lema de Thue

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.