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$
102. Quadrati con 1,2,5
-
- Messaggi: 62
- Iscritto il: 22 nov 2010, 19:09
- Località: Sto ca... Stoccarda!
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]
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]
Ultima modifica di bĕlcōlŏn il 04 ago 2011, 16:06, modificato 1 volta in totale.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Re: 102. Quadrati con 1,2,5
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
-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
Ultima modifica di bĕlcōlŏn il 04 ago 2011, 16:06, modificato 1 volta in totale.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
-
- Messaggi: 62
- Iscritto il: 22 nov 2010, 19:09
- Località: Sto ca... Stoccarda!
Re:
questo è vero se $p\neq 2$.. completa e poi ti lascio mettere il prossimobĕlcōlŏn ha scritto:se $p\neq 3$, allora sicuramente $3n+4$ è un sistema completo di residui modulo $p$, quindi non può essere sempre residuo quadratico
qua intendevi ovviamente $\gcd(y+1,y-1)\mid 2$bĕlcōlŏn ha scritto:Siccome $2|\gcd(y+1,y-1)$
in ogni caso, complimenti per la chiarezza
Re: Re:
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$.Nabir Albar ha scritto:questo è vero se $p\neq 2$.. completa e poi ti lascio mettere il prossimobĕlcōlŏn ha scritto:se $p\neq 3$, allora sicuramente $3n+4$ è un sistema completo di residui modulo $p$, quindi non può essere sempre residuo quadratico
Corretto!Nabir Albar ha scritto:qua intendevi ovviamente $\gcd(y+1,y-1)\mid 2$bĕlcōlŏn ha scritto:Siccome $2|\gcd(y+1,y-1)$
Grazie! Posso sapere da dove l'hai preso il problema?Nabir Albar ha scritto: in ogni caso, complimenti per la chiarezza
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
-
- Messaggi: 62
- Iscritto il: 22 nov 2010, 19:09
- Località: Sto ca... Stoccarda!
Re: 102. Quadrati con 1,2,5
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?
Cmq c'è anche una soluzione che non usa Dirichlet ma le equazioni di Pell, chi ci prova?