Alla ricerca della perfezione

[Ratman98]

Il problema è il seguente: dobbiamo trovare tutti gli n tali che 3^n + 1 è un quadrato perfetto.Innanzitutto mi scuso per non usare LaTeX,devo ancora imparare(tutto ). In realtà ho risolto il problema, ma ricorrendo al modulo 4; ho trovato che la radice del quadrato deve essere della forma 4k+2 e poi che k=0, quindi n=1. Questo problema però è il primo di quelli che seguono la settima lezione del corso di preparazione alle olimpiadi tenuto dal prof. Callegari e rientra nella categoria di quelli quasi uguali a quelli già mostrati nella lezione, dove si ricorre sempre ad un modulo x se si ha x^n+ altro. Vorrei quindi sapere se c'è una risoluzione che sfrutta il modulo 3 , perché io non ne ho trovate.

[jordan]

In realtà ho risolto il problema, ma ricorrendo al modulo 4

Perchè quel "ma"? Usare le non congruenze non vuole dire barare

ho trovato che la radice del quadrato deve essere della forma 4k+2 e poi che k=0, quindi n=1.

Qui non ti seguo: nel senso, $3^n+1$ è quadrato. Modulo $4$ tutti i quadrati devono avere resto $0$ oppure $1$. Ma $3^n+1$ è somma di dispari (quando $n\neq 0$), quindi deve essere un numero pari. Significa il resto modulo $4$ deve essere per forza $0$. Quindi $n$ deve essere per forza dispari. Ti trovi nella condizione di risolvere l'equazione $3^{2k+1}+1=x^2$. Ora?

Vorrei quindi sapere se c'è una risoluzione che sfrutta il modulo 3 , perché io non ne ho trovate.

Non tutti i moduli funzionano, nè è detto che usare moduli nelle diofantee ti porti a trovare le soluzioni, se esistono. In questo case facendo modulo $3$, oppure $9$ (o qualche altra potenza di 3), non puoi concludere niente perchè $3^n+1 \equiv 1\pmod{3^k}$ ogni volta che $n$ è maggiore di $k$, e $1$ è sempre un residuo quadratico, modulo qualunque $3^k$..

Completiamo la soluzione?

[Ratman98]

Spero di riuscire a spiegarmi.3^n+1 mod4 è sempre congruo a 2 per n pari e a 0 per n dispari. Ora, qualsiasi quadrato di radice 4k+1,4k+2,4k+3 non è congruo a 2 e l'unico congruo a 0 è quello di radice della forma 4k+2, quindi anche la radice del nostro quadrato perfetto è di questa forma(oltre al fatto che l'indice è per questo sicuramente dispari).A questo punto: 3^n + 1= (4k+2)^2, da cui
3^n= 16k^2 + 16k + 3= 16k^2+4k+12k+3=(4k+3)(4k+1). Il primissimo membro è una potenza di 3, quindi le due parentesi dell'ultimo membro devono essere potenze di 3. Notiamo che la differenza tra le parentesi è 2, il che significa che non possono essere entrambe congrue a 0 mod3, cioè una deve essere 3^0=1. Se proviamo ad uguagliare ad 1 le due parentesi notiamo che solo la seconda può essere uguale ad 1 perché altrimenti avremo k=1\2. Quindi k=1 e n=0.
Attendo una tua conferma o anche una(ma non mi pare) smentita

[jordan]

Ora, qualsiasi quadrato di radice 4k+1,4k+2,4k+3 non è congruo a 2 e l'unico congruo a 0 è quello di radice della forma 4k+2

Ci sono almeno due grandi falle nel tuo ragionamento:

1) Quello che è sottolineato sopra non è corretto, come si corregge?

2) Da dove tiri fuori la soluzione $n=1$?

[Ratman98]

1) (4k+1)^2 è congruo ad 1 mod4. (4k+2)^2 è congruo a 0 mod4. (4k+3)^2 è congruo a 1 mod4
3^n + 1 è sempre congruo a 0 mod4 per n dispari e l'unica radice(vedi sopra) il cui quadrato mod4 è congruo a 0 è 4k+2. Ti prego di corregermi qualora mi sbagliassi a questo punto, perché senza questo cade effettivamente tutto il ragionamento
2) Qui ho sbagliato a scrivere , perché se k=0, n=1. Infatti: 3^n + 1= (4k+2)^2= {4(0)+2}^2=2^2=4
Da cui 3^n= 4-1=3 . L'uguaglianza è rispettata solo nel caso in cui n=1.
Qui credo non ci siano errori

[jordan]

1) (4k+1)^2 è congruo ad 1 mod4. (4k+2)^2 è congruo a 0 mod4. (4k+3)^2 è congruo a 1 mod4
3^n + 1 è sempre congruo a 0 mod4 per n dispari e l'unica radice(vedi sopra) il cui quadrato mod4 è congruo a 0 è 4k+2. Ti prego di corregermi qualora mi sbagliassi a questo punto, perché senza questo cade effettivamente tutto il ragionamento

E i multipli di $4$? Non hai che $(4k)^2 \equiv 0\pmod{4}$? [Se usi il modulo $n$ e vuoi risolvere le cose "a mano" hai sempre $n$ casi!]

2) Qui ho sbagliato a scrivere , perché se k=0, n=1. Infatti: 3^n + 1= (4k+2)^2= {4(0)+2}^2=2^2=4
Da cui 3^n= 4-1=3 . L'uguaglianza è rispettata solo nel caso in cui n=1.
Qui credo non ci siano errori

Ora è ok, basta completare il caso rimanente (vedi sopra)

[Ratman98]

Se m=4k m^2 è un multiplo di 16. Però a quel punto m^2=3^n + 1= 16j, il che non può essere.Scartiamo quindi il caso m=4k e ci dedichiamo al caso m=4k+2, come prima. E il problema è risolto.Dico che 3^n +1 non può essere uguale a 16j perché 3^n è congruo mod16 a 1, 3, 9 o 11

[jordan]

Bene, ora è tutto apposto

[Ratman98]

Innanzitutto ti ringrazio, perché ho avvertito nella tua "pignoleria" la premura di un animo gentile(come tutti qui nel forum).Lo stesso mi pare che prima tu abbia accennato(indirettamente) a un metodo per analizzare tutti i casi non "a mano" e mi piacerebbe conoscerlo . Ancora prima hai scritto che 1 è un residuo quadratico mod3^n per qualsivoglia n , ma , e qui quasi svengo nello sforzo di ricordare un numero è un residuo quadratico rispettivamente ad un modulo p con p primo e 3^2 ad esempio non è primo

[jordan]

Un intero $x$ si definisce "residuo quadratico" modulo $n$ se esiste un intero $y$ tale che $x\equiv y^2 \pmod{n}$. Con questa definizione ci sei che $1$ e $0$ sono sempre residui quadratici? Nel problema, è utile memorizzare i residui quadratici modulo "importanti"; per esempio, quelli modulo 4, modulo 3, modulo 8, modulo 5..

Poi esistono tecniche molto conosciute che aiutano in questo tipo di problemi. Per questo in particolare, l'equazione da risolvere è $3^n+1=m^2$ negli interi, che equivale a
$$a^b-c^d=1$$
con il vincolo che $b=2$ e $c=3$. In pratica, l'equazione generale chiede quando due potenze perfette sono consecutive. Qui sono risolti parecchi casi, dai un'occhiata agli ultimi

[Ratman98]

Con p intendi un qualsiasi numero primo, giusto? Se è così 0 e 1 sono sempre congrui in un modulo qualunque ai loro quadrati(cioè 0 e 1), ma non c'è nessun p tale da dividere 1 (1 non è primo) e quindi in base alla tua definizione non può essere un residuo quadratico; oppure ho preso fischi per fiaschi?
P.S. : non vedo l'ora di riuscire a trovare il tempo necessario a studiare le dispense(faccio bene a chiamarle così?) verso le quali mi hai indirizzato, anche se l'inglese per me è un buon deterrente

[jordan]

Con p intendi un qualsiasi numero primo, giusto? Se è così 0 e 1 sono sempre congrui in un modulo qualunque ai loro quadrati(cioè 0 e 1), ma non c'è nessun p tale da dividere 1 (1 non è primo) e quindi in base alla tua definizione non può essere un residuo quadratico; oppure ho preso fischi per fiaschi?

Non avevo visto la risposta, mi spiace. Riscrivo la definizione, mi ero scappato un $p$ che non c'entrava nulla.

Allora, prendi un intero positivo $n$. Un intero $m$ è detto residuo quadratico modulo $n$ se esiste un intero $x$ tale che $n$ divide $x^2-m$. Ora se $m$ è $0$ ( o un multiplo di $n$) allora è sufficiente prendere $x=m$, quindi $0$ è sempre un residuo quadratico. Se invece $m=1$ (oppure un intero della forma $kn+1$) allora è sufficiente prendere $x=1$. Infatti $n$ divide sempre $x^2-m$. Quindi anche $1$ è sempre un residuo quadratico modulo $n$.

[karlosson_sul_tetto]

Un intero $m$ è detto residuo quadratico modulo $n$ se esiste un intero $x$ tale che $n$ divide $x^n-m$.

Sono io ad essere fuso, o è un typo? Non dovrebbe essere $x^2-m$?

[simone256]

Credo sia un typo, ma credo anche che tu sia fuso

[Ratman98]

Grazie, ora tutto torna .