OliForum Matematico

Ecco un bel quesito da MathLinks:

Sia $ p $ a prime number: $ p = 4k+3 $ for some $ k \in N $. Sia $ a \in Z $.
Risolvere:
$ 3a^2 + 1 = p^2 $.

Su MathLinks Rust lo risolve così:

Soluzioni nei naturali $ x^2 - 3a^2 = 1 $:
$ x(n)= \frac{1}{2} \cdot [ (2 + \sqrt{3})^n + (2 - \sqrt{3})^n ] $,
$ a(n) = \frac{(2+ \sqrt{3})^n - (2 - \sqrt{3})^n}{2 \sqrt{3} } $,
con $ n =1,2,3,... $
$ x(2k+1) $ è pari.
$ x(4k) \equiv 1 (mod 4) \Leftrightarrow x(4k+2) \equiv 3 (mod 4) $.
Se $ p(n) | x(n) $ e "Simbolo di Legendre" $ \frac{3}{p(n)} = 1 $, allora $ p(n) | x(kn) \forall k $ dispari .
Pertanto le x sono del tipo $ x(4k+2) $. Uno di esso $ x(2)=7 $ è primo.

Chiedendogli informazioni ha scritto che necessariamente deve essere:

$ x(0)=1,x(1)=2, x(n+1)=4x(n)-x(n-1) $.

Ora, se questo fosse vero allora è facile esplicitare $ x(n) $ in funzione di n perchè è una successione definita per ricorrenza.

Il problema è: da dove stabilisce che vale
$ x(0)=1,x(1)=2, x(n+1)=4x(n)-x(n-1) $

Potreste aiutarmi ??? Scusate l'ignoranza...

Nessuno risponde perchè è troppo banale???

Premetto di non aver letto con attenzione la soluzione sopra... credo di averne fatta una molto diversa, che non usa teoria avanzata di nessun genere.

Riscrivo l’equazione come $ 3a^2=(p-1)(p+1)=8(2k+1)(k+1) $; dato che $ 2k+1 $ è dispari e al primo membro i fattori 2 sono presenti con esponente pari, $ k $ deve essere dispari. Lo pongo uguale a $ 2h-1 $. Da qui si ricava che $ p=8h-1 $.
Sostituendo nuovamente nell’originale questa formula per p si ricava $ 3a^2=16(4h-1)h $. Ora noi sappiamo che $ MCD(4h-1, h)= MCD(4h-1, 4h)=1 $; dunque i due fattori $ 4h-1 $ e $ h $ sono della forma $ 3x^2 $, $ y^2 $.
1. Supponiamo che $ 4h-1=x^2 $ e $ h=3y^2 $: nella prima si ottiene un assurdo mod4, perché il primo membro viene congruo a 3.
2.Dunque deve essere vero che $ 4h-1=3x^2 $ e che $ h=y^2 $; sostîtuisco quest'ultima espressione nella relazione iniziale su p e ottengo $ p=8y^2-1 $. Dalla prima, inoltre, ottengo $ 4h-1=\frac{p-1}{2}=3x^2 $, cioè $ p=6x^2+1 $, dove x è dispari, perché altrimenti si otterrebbe che $ p\equiv1 $ mod 8, che contraddice l’altra espressione di p.

Analizzo ora la relazione iniziale mod 7: i residui quadratici mod 7 sono, in ordine, 0, 1, 2, 4, 4, 2, 1. Sostituisco i possibili valori per $ a^2 $:

1. $ a^2\equiv2 $: si ottiene $ p^2\equiv0 $, cioè $ p=7 $$, che effettivamente è soluzione;

2. $ a^2\equiv4 $: si ottiene $ p^2\equiv-1 $, impossibile

3. $ a^2\equiv1 $: si ottiene $ p^2\equiv4 $, cioè $ p\equiv5 $ o $ p\equiv2 $; pero’ avevo detto sopra che $ p=8y^2-1\equiv y^2-1 $; se fosse vera una qualsiasi di queste congruenze su p si avrebbe che 3 e 6 dovrebbero essere residui quadratici, che è falso;

4. $ a^2\equiv0 $: qui arrivano i problemi. Innanzitutto si ottiene $ p\equiv1 $ o $ p\equiv-1 $.
Analizzo i due casi separatamente:

4.1 $ p\equiv1 $
Sapendo che $ p=6x^2+1 $, si ottiene che $ x=7b $, con b dispari; sostituendo nella relazione iniziale e semplificando un fattore 3 si ottiene che:
$ a^2=4*7^2*b^2* (3*7^2*b^2+1) $. Da qui si ricava che deve essere:
$ c^2=3*7^2*b^2+1 $, cioè
$ 3*7^2*b^2= (c-1)(c+1) $, con c pari e quindi gli ultimi due fattori coprimi. Chiamando
$ z=7b $, si ottengono 2 casi:
4.1.1 $ c-1=x^2 $, $ c+1=3y^2 $, che implica $ 3x^2+2=y^2 $, impossibile per le congruenze mod 3.
4.1.2 $ c-1=3x^2 $, $ c+1=y^2 $, che implica $ x^2+2=3y^2 $ ; sapevamo pero’ anche che almeno uno tra $ c-1 $ e $ c+1 $ è congruo a 0 mod 7. Supponiamo $ x\equiv0 $: si ottiene $ y^2\equiv3 $, impossibile. Supponiamo $ y\equiv0 $: si ottiene $ x^2\equiv5 $, impossibile.

4.2$ p\equiv-1 $
Sapendo che $ p=8y^2-1\equiv y^2-1 $, si ottiene $ y=7b $; sostituendo nella relazione iniziale si ottiene che:
$ 3a^2=16*7^2*b^2* (4*7^2*b^2-1) $. Da qui si ricava che deve essere:
$ 3c^2=4*7^2*b^2-1=(14b+1)(14b-1) $. I due fattori sono coprimi, dunque si dovrebbe verificare una di queste due situazioni, che pero’ sono impossibili:
4.2.1 $ 14b-1=x^2 $, $ 14b+1=3y^2 $, che implica dalla prima $ x^2\equiv-1 $ mod7, impossibile.
4.2.2 $ 14b-1=3x^2 $, $ 14b+1=y^2 $, che implica $ y^2=3x^2+2 $, impossibile mod 3.

Fine

Mamma mia quanto è lungo ‘sto post… ora spero che qualcuno abbia voglia di controllarla,perchè data l’ora potrei aver fatto stupidaggini.
Ciao
Maria

Si, anche la mia soluzione era di questo tipo, rimboccandomi le maniche e provando le varie congruenze...
Ma se riuscissimo a comprendere il perchè di quella successione allora sarebbe tutto più bello e ... alternativo!
Cmq adesso chiedo al mio prof. Ci si aggiorna!

io credo che soluzioni di questo genere(con la successione) ci siano per tutte le equazioni del tipo
$ x^2-dy^2=1 $
usando la scomposizione
$ (x-\sqrt d)(x+\sqrt d)=1 $
ma poi non so andare avanti perchè di queste cose non ci capisco molto...

ciao ciao

C'è un argomento "di teoria quasi-olimpica" abbastanza avanzato, che parla delle equazioni di questo tipo; le equazioni diofantee del tipo
$ x^2-dy^2=1 $ si chiamano equazioni di Pell (vedi anche su Mathworld).
Alcuni fatti sparsi che mi ricordo al volo su di esse...
1) (mi sembra) ha infinite soluzioni per ogni scelta di d
2) una volta trovata la soluzione più piccola x_0, y_0 copiandola dal vicino di banco, tutte le soluzioni sono date da $ x_n+\sqrt d y_n=(x_0+\sqrt d y_0)^n $
3) la soluzione più piccola si trova a occhio oppure a colpi di martello con la teoria delle frazioni continue (che è abbastanza complicata)
4) un libro che tratta di queste cose in modo abbastanza elementare è il Davenport, /Aritmetica superiore/. E' un libricino verde che era tra i possibili premi all'ultimo Cesenatico (Maria, almeno tu dovresti averlo, se non ricordo male...)
(quindi già che ci sei puoi anche controllare che non ci sia qualcosa di sbagliato o qualche ipotesi dimenticata nei fatti che ho elencato )

Se vi capita questa equazione in una gara credo che possiate claimare tranquillamente quanto sopra se citate la parola magica "Pell's equation".
Tremate, il "syllabus" delle IMO cresce di anno in anno...
ciao,
--f

Aaargh, mi perdo sempre i topic più belli...dunque, credo che l'iter sia:
Equazione di base: $ x^2-3a^2=1 $.
Differenza di quadrati, quindi possiamo o andare giu di goniometria o sfruttare le potenze: dico questo perche la differenza dei quadrati è uguale a $ 1=\sin^2\alpha+\cos^2 \alpha $; oppure, sfruttando le potenze, vedendo che è un prodotto pari a 1, nello sviluppo della potenza di un binomio possiamo "togliere" ad ogni addendo il fattore$ 1^k=(x-\sqrt{3}a)^k(x+\sqrt{3}a)^k=1^k=1 $. Da qui in poi fra residui e quadratici e simboli di Jacobi non è competenza mia

Si avete ragione riguardo all'equazione di Pell, trovate un bel paragrafo con dimostrazione anche su "Problem Solving Strategies", Springer editore (dimenticavo, in Inglese )

Cmq la domanda iniziale è: da dove salta fuori la successione fatta in quel modo?

Gauss_87 ha scritto:Si avete ragione riguardo all'equazione di Pell, trovate un bel paragrafo con dimostrazione anche su "Problem Solving Strategies", Springer editore (dimenticavo, in Inglese )

Cmq la domanda iniziale è: da dove salta fuori la successione fatta in quel modo?

Beh, sono le soluzioni dell'equazione di Pell generate a partire da $ x_0=2, a_0=1 $. Prendi la formula generica $ x_n+\sqrt 3 a_n = (2+\sqrt 3)^n $, la "coniughi" e ottieni $ x_n-\sqrt 3 a_n = (2-\sqrt 3)^n $, metti a sistema le due e risolvi per trovare $ x_n $ e $ a_n $.
Poi il passaggio equazione per ricorrenza<->somma di potenze n-esime è standard, anche se di solito si vede nell'altro verso (es. schede di Gobbino).

ciao,
--f

Grazie fph...adesso ci provo...
Cmq te 6 Federico Poloni???