102. Quadrati con 1,2,5

[Nabir Albar]

Sia $b>5$ un intero. Sia $x_n$ il numero che in base $b$ si scrive come $\underbrace{11\cdots1}_{n - 1}\underbrace{22\cdots2}_{n}5$.
Allora $x_n$ è un quadrato perfetto per ogni $n$ sufficientemente grande sse $b=10$

[bĕlcōlŏn]

Inizio scrivendo che $\underbrace{11\cdots1}_{n - 1}\underbrace{22\cdots2}_{n}5 = 3+\dfrac{b^{n+1}-1}{b-1}+\dfrac{b^{2n}-1}{b-1}$. Se $b=10$ è semplice verificare che $3+\dfrac{10^{n+1}-1}{9}+\dfrac{10^{2n}-1}{9} = \left(2+3\dfrac{10^n-1}{9}\right)^2$, e quindi se $b=10$, $x_n$ è un quadrato per ogni $n$ naturale, e una freccia è andata.

Ora faccio l'altra. Per ipotesi esiste un certo $M$ tale che per ogni $n\geq M$, allora $x_n$ è un quadrato. Voglio mostrare che allora $x_n$ è un quadrato anche con $n<M$. Per fare ciò, lavoro con i primi $p>max(M,b)$. Ora, per ipotesi so che, per ogni $1\leq k\leq M-1<p-1$, esiste un certo $n\geq M$, e $n \equiv k \pmod{p-1}$, tale che $x_n$ è un quadrato. Ma allora analizzando modulo $p$, si ha che $x_n \equiv 3+\dfrac{b^{n+1}-1}{b-1}+\dfrac{b^{2n}-1}{b-1} \equiv 3+\dfrac{b^{k+1}-1}{b-1}+\dfrac{b^{2k}-1}{b-1} \pmod p$. Quindi per tutti i $1 \leq i \leq M$, si ha che $x_i$ è un residuo quadratico modulo tutti i primi maggiori di $max(M,b)$.

A questo punto vorrei dimostrare che se un numero $a$ è residuo quadratico modulo tutti i primi maggiori di una certa costante, allora $a$ è un quadrato.
Suppongo che non lo sia: Sia $a=p_1^{a_1}\cdot p_2^{a_2}\cdot \dots p_n^{a_n}$ la sua fattorizzazione. Per la moltiplicatività del simbolo di Legendre dato un certo primo $q$ $\left(\dfrac{a}{q}\right) = \displaystyle\prod_{i=1}^n \left(\dfrac{p_i}{q}\right)^a_i$. Non essendo $a$ un quadrato, ci sarà sicuramente un $a_i$ dispari. Scelgo, allora, $q$ in modo che $\left(\dfrac{p_i}{q}\right) = -1$ e faccia $1$, invece, con tutti i $p_j$, con $j\neq i$ (questo lo posso fare con la reciprocità quadratica, ad esempio). Allora avrò che $\left(\dfrac{a}{q}\right)=-1$ per alcune condizioni $q \equiv k_1\pmod{p_1}\dots q\equiv k_n \pmod{p_n}$. Allora per il teorema cinese del resto, $q=A \pmod{\displaystyle\prod_{i=1}^n p_i}$ per una certa $A$ e siccome per Dirichlet esistono infiniti di questi $q$, ne esisteranno infiniti maggiori di una certa costante, e quindi assurdo, perché per questi primi $a$ non sarebbe residuo.

Ora so che $x_n$ è sempre un quadrato. Allora sia $p|b-1$ un primo. E' chiaro che $x_n \equiv 3n+4 \pmod p$ per ogni $n$. Ciò vuol dire che per ogni $n$, $3n+4$ è un residuo quadratico modulo $p$. Se $p=3$ siamo a posto, ma se $p\neq 3$, allora sicuramente $3n+4$ è un sistema completo di residui modulo $p$, quindi non può essere sempre residuo quadratico. Dunque $b=3^k+1$ per qualche $k$. [Continua nell'altro post]

[bĕlcōlŏn]

Concludo (spero!): Dei fatti precedenti qui riutilizzo che $b=3^k+1$, e che sono tutti quadrati. Ora scelgo $p>b$, prendo $n \equiv -1 \pmod{p-1}$ e ho che $x_n \equiv 3 + \dfrac{b^{n+1}-1}{b-1} + \dfrac{b^{2n}-1}{b-1} \equiv 3 + \dfrac{\frac{1}{b^2}-1}{b-1} \equiv 3 - \dfrac{b^2-1}{b^2(b-1)} \equiv 3 - \dfrac{b+1}{b^2} \equiv x^2 \pmod p$ per qualche $x$. Allora posso moltiplicare per $b^2$ essendo invertibile e ottengo $3b^2-b-1 \equiv (bx)^2 \pmod p$. Quindi, $3b^2-b-1$ è quadrato per infiniti primi, e allora $3b^2-b-1$ è un quadrato per quanto detto prima. Ora sostituendo si ha $3(3^k+1)^2-(3^k+1)-1=3(3^{2k}+2\cdot 3^k +1) - 3^k - 2 = 3^{2k+1}+5\cdot 3^k + 1 = y^2$. Dunque $3^k(3^{k+1} + 5) = (y+1)(y-1)$. Siccome $\gcd(y+1,y-1)|2$, allora si possono avere due casi:
-Caso 1: $y+1=3^k\cdot t$ e $y-1=\dfrac{3^{k+1}+5}{t}$. Quindi $3^kt -2 = \dfrac{3^{k+1}+5}{t}$. Suppongo $t\geq 3$. Allora $3^kt-2 \geq 3^{k+1}-2$ e $\dfrac{3^{k+1}+5}{t} \leq 3^k + 2$. Quindi, grazie all'uguaglianza ottengo $3^{k+1}-2 \leq 3^k+2 \Leftrightarrow 2\cdot 3^k \leq 4$. Quindi $k=0$, che dà $b=2$, contro le ipotesi. Ora se $t=1$ si ha $3^k-2=3^{k+1}+5$ che non ha soluzione. Se $t=2$ si ha $4\cdot 3^k - 4 = 3^{k+1}+5$, ovvero $3^k=9$, che dà $b=10$, che funziona sempre.
-Caso 2: $y-1=3^k\cdot t$ e $y+1=\dfrac{3^{k+1}+5}{t}$. Quindi $3^k\cdot t + 2=\dfrac{3^{k+1}+5}{t}$. Se $t\geq 3$ come prima ho $3^k+2\geq 3^{k+1}+2$, assurdo. Rimangono i casi $t=1$, che non dà soluzioni, e $t=2$ che dà $4\cdot 3^k + 4 = 3^{k+1}+5$, da cui $k=0$ che dà $b=2$, assurdo per le ipotesi.

Spero sia chiaro (la parte in cui dimostro che tutti gli elementi della successione sono dei quadrati è un di più, perché $x_n \equiv 3n+4$ è anche un quadrato definitivamente, quindi non mi servono che tutti sia quadrati).

Spero sia corretta

[Nabir Albar]

se $p\neq 3$, allora sicuramente $3n+4$ è un sistema completo di residui modulo $p$, quindi non può essere sempre residuo quadratico

questo è vero se $p\neq 2$.. completa e poi ti lascio mettere il prossimo

Siccome $2|\gcd(y+1,y-1)$

qua intendevi ovviamente $\gcd(y+1,y-1)\mid 2$

in ogni caso, complimenti per la chiarezza

[bĕlcōlŏn]

se $p\neq 3$, allora sicuramente $3n+4$ è un sistema completo di residui modulo $p$, quindi non può essere sempre residuo quadratico

questo è vero se $p\neq 2$.. completa e poi ti lascio mettere il prossimo

Hai ragione... comunque per quanto detto, $2b+5$ e $3b^2-b-1$ sono quadrati. Considero modulo 4 tali espressioni. L'unico valore per cui questi sono entrambi residui quadratici è $b \equiv 2 \pmod 4$, quindi $2 \nmid b-1$.

Siccome $2|\gcd(y+1,y-1)$

qua intendevi ovviamente $\gcd(y+1,y-1)\mid 2$

Corretto!

in ogni caso, complimenti per la chiarezza

Grazie! Posso sapere da dove l'hai preso il problema?

[Nabir Albar]

Dalla Shortlist delle IMO del 2003. A te il prossimo
Cmq c'è anche una soluzione che non usa Dirichlet ma le equazioni di Pell, chi ci prova?