Alla ricerca della perfezione
Alla ricerca della perfezione
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.
Re: Alla ricerca della perfezione
Perchè quel "ma"? Usare le non congruenze non vuole dire barareRatman98 ha scritto:In realtà ho risolto il problema, ma ricorrendo al modulo 4
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?Ratman98 ha scritto: ho trovato che la radice del quadrato deve essere della forma 4k+2 e poi che k=0, quindi n=1.
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$..Ratman98 ha scritto:Vorrei quindi sapere se c'è una risoluzione che sfrutta il modulo 3 , perché io non ne ho trovate.
Completiamo la soluzione?
The only goal of science is the honor of the human spirit.
Re: Alla ricerca della perfezione
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
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
Re: Alla ricerca della perfezione
Ci sono almeno due grandi falle nel tuo ragionamento:Ratman98 ha scritto: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
1) Quello che è sottolineato sopra non è corretto, come si corregge?
2) Da dove tiri fuori la soluzione $n=1$?
The only goal of science is the honor of the human spirit.
Re: Alla ricerca della perfezione
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
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
Re: Alla ricerca della perfezione
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!]Ratman98 ha scritto: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
Ora è ok, basta completare il caso rimanente (vedi sopra)Ratman98 ha scritto: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
The only goal of science is the honor of the human spirit.
Re: Alla ricerca della perfezione
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
Re: Alla ricerca della perfezione
Bene, ora è tutto apposto
The only goal of science is the honor of the human spirit.
Re: Alla ricerca della perfezione
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
Re: Alla ricerca della perfezione
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
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
Ultima modifica di jordan il 12 set 2014, 23:28, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.
Re: Alla ricerca della perfezione
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
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
Re: Alla ricerca della perfezione
Non avevo visto la risposta, mi spiace. Riscrivo la definizione, mi ero scappato un $p$ che non c'entrava nulla.Ratman98 ha scritto: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?
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$.
Ultima modifica di jordan il 13 set 2014, 14:01, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.
- karlosson_sul_tetto
- Messaggi: 1454
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: Alla ricerca della perfezione
Sono io ad essere fuso, o è un typo? Non dovrebbe essere $x^2-m$?jordan ha scritto: Un intero $m$ è detto residuo quadratico modulo $n$ se esiste un intero $x$ tale che $n$ divide $x^n-m$.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
Re: Alla ricerca della perfezione
Credo sia un typo, ma credo anche che tu sia fuso
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
Re: Alla ricerca della perfezione
Grazie, ora tutto torna .