Newsgroup: it.hobby.enigmi
Titolo: Primi e Fibonacci

Rileggendo lo scrigno di enigmi di Paolo Licheri
http://web.tiscalinet.it/paololicheri/home.htm
sotto Numeri --> Primi e Fibonacci,
vedo un intervento di un acerbo enigmista in erba che
si firma in modo anonimo come Cxxxs ;)
Lo rilancio (sperando di rovinare le nottate di qualcun altro)
---------------------------------------------------------------
i numeri di Fibonacci, la relazione di ricorrenza,
il rapporto aureo e la formula di Binet credo siano +/ noti a tutti,
qui ci si occupava di fattorizzazioni.
Eccone una tavola :
 F_1 = 1
 F_2 = 1
 F_3 = 2 
 F_4 = 3 
 F_5 = 5 
 F_6 = 2^3 
 F_7 = 13 
 F_8 = 3 * 7 
 F_9 = 2 * 17 
F_10 = 5 * 11 
F_11 = 89 
F_12 = 2^4 * 3^2 
F_13 = 233 
F_14 = 13 * 29 
F_15 = 2 * 5 * 61 
F_16 = 3 * 7 * 47 
F_17 = 1597 
F_18 = 2^3 * 17 * 19 
F_19 = 37 * 113 
F_20 = 3 * 5 * 11 * 41 
F_21 = 2 * 13 * 421 
F_22 = 89 * 199 
F_23 = 28657 
F_24 = 2^5 * 3^2 * 7 * 23 
F_25 = 5^2 * 3001 
F_26 = 233 * 521 
F_27 = 2 * 17 * 53 * 109 
F_28 = 3 * 13 * 29 * 281 
F_29 = 514229 
F_30 = 2^3 * 5 * 11 * 31 * 61 
F_31 = 557 * 2417 
F_32 = 3 * 7 * 47 * 2207 
F_33 = 2 * 89 * 19801 
F_34 = 1597 * 3571 
F_35 = 5 * 13 * 141961 
F_36 = 2^4 * 3^3 * 17 * 19 * 107 
F_37 = 73 * 149 * 2221 
F_38 = 37 * 113 * 9349 
F_39 = 2 * 233 * 135721 
F_40 = 3 * 5 * 7 * 11 * 41 * 2161 
F_41 = 2789 * 59369 
F_42 = 2^3 * 13 * 29 * 211 * 421 
F_43 = 433494437 
F_44 = 3 * 43 * 89 * 199 * 307 
F_45 = 2 * 5 * 17 * 61 * 109441 
F_46 = 139 * 461 * 28657 
F_47 = 2971215073 
F_48 = 2^6 * 3^2 * 7 * 23 * 47 * 1103 
F_49 = 13 * 97 * 6168709 
F_50 = 5^2 * 11 * 101 * 151 * 3001 
L'enunciato che interessava, solo leggermente indebolito,
con valore di congettura (anche se e' un teorema), e' [Silvio Sergio] :
	Sia p un primo dispari :
	  i) se p=1 o 9(mod10) allora p|F_(p-1)		(1.1)
	 ii) se p=3 o 7(mod10) allora p|F_(p+1)		(1.2)
come si vede in
p=11 | F_10 = 5 * 11 
p=19 | F_18 = 2^3 * 17 * 19 
p=23 | F_24 = 2^5 * 3^2 * 7 * 23 
p=17 | F_18 = 2^3 * 17 * 19
Fuori dal teorema restano solo i numeri primi 2 (che puo' essere fatto rientrare
nel caso ii) e 5 per cui vale p|F_p
E' stato invece dimostrato [Maurizio Codogno] :
	Dato m, esiste un k<m^2 tale che m|F_k		(2)
Infine, io stesso ho concluso, dopo ca. 30 righe di una dim. esasperante :
	Dato p primo, esiste un k<p+1 tale che p|F_k	(3)
---------------------------------------------------------------------------
Io ho le dimostrazioni (abbastanza decenti, adesso) delle seguenti :
1) il teorema (1.1) ovvero se p=+/-1(mod5) allora p|F_(p-1)
2) se p=+/-1(mod5) e' un fattore *primitivo* di F_n allora p=1(mod n)
[e l'analogo 'Se p=+/-2(mod5)...' per cui vale p=-1(mod n), ma in cui occorre (1.2)]
Le postero' al piu' presto, quando avro' un ritaglio di tempo,
intanto c'e' un risultato che e' fuori dalla mia portata :
3) Siano p e n dispari, allora se p e' un fattore primitivo di F_n allora p=1(mod4)
oooops... non ho definito 'primitivo', tempo!tempo!
Qualunque commento e' gradito.

 2) se p=+/-1(mod5) e' un fattore *primitivo* di F_n allora p=1(mod n)
Un fattore primitivo si spiega cosi' :
non e' difficile mostrare che dato un indice n, F(n) divide tutti i numeri
di Fibonacci con indice multiplo, F(mn). Piu' in generale si ha, con p primo
o composto che sia:
p|F(n) => p|F(mn)
Questo significa che se si vuole fattorizzare un numero F_k, ci sono dei
fattori molto semplici da calcolare, e sono tutti i fattori di F_p con
p divisore di k. Tutti gli altri fattori primi si dicono primitivi.
La definizione e' allora :
p e' un divisore primitivo di F_k sse non e' divisore di F_p con p|k.
Infine, osservazione fondamentale, dato un p primo, esiste un periodo T
di divisibilita' per p dei numeri F_nT.
(Dev'essere circa una copia di cio' che si dimostra per i numeri di
Mersenne o dei Repunit in gererale, usando il piccolo th. di Fermat)
Dim. Sia p un fattore di Fn, p|Fn, della forma p=+/-1 (mod5), dal precedente
si ha p|F_(p-1), da quanto detto risulta quindi che n deve essere un multiplo
del periodo di div. T per p, che e' a sua volta un divisore di (p-1).
Supponiamo che q sia un divisore di n (distinto da 1, questo caso si scarta
facilmente), che sia il periodo T, si avrebbe allora F_q=0(modp), ma in tal
caso si ha p|Fq, ovvero p non e' un fattore primitivo.
Escludendo tale caso deve essere allora T=n e quindi n|(p-1) che e' la tesi.

          ii) se p=3 o 7(mod10) allora p|F_(p+1)         (1.2)
Dim. Partendo ancora dalla seguente,
     ((1+sqr(5))^n-(1-sqr(5))^n  
F_n = -------------------------
             sqr(5)*2^n
Il problema della non esistenza della radice di 5 si risolve cosi' :
se si scrive j^2=q, con q un non residuo, con l'aggiunta di questo
nuovo elemento si genera un ampliamento del campo (mod p), i cui
elementi sono della forma a+jb, che e' ancora un campo, se il modulo
e' inteso calcolato su entrambe le componenti 'a' e 'b' e se si opera
con le normali regole di calcolo, analogamente a come si farebbe coi
numeri complessi, sostituendo j^2 all'occorrenza.
Posto senz'altro j^2=5, allora :
P|F_n sse F_n=[(1+j)^n-(1-j)^n)]/(j*2^n)=0 (mod p)
(1+j)^n=(1-j)^n  (mod p)
c^n = 1 (mod p)
poiche' il gruppo moltiplicativo del nuovo campo ha ordine n^2-1,
l'ugualianza vale certamente per p=n^2-1, ma si puo' fare di meglio :
c e' un rapporto z/(z*), ossia tra un numero complesso ed il suo coniugato,
che compone evidentemente un sottogruppo moltiplicativo
C = { c=z/z*, con z=a+jb (mod p*)}
un c non varia se si moltiplica il suo generatore z per un reale puro,
viceversa c1=c2 sse z1/(z1*)=z2/(z2*), poiche' esiste sempre un elemento
r tale che z2=r*z2, segue z1/(z1*)=(r*z1)/(r*z1)* cioe' r=r*, r e' reale.
Cioe' se due elementi di C sono uguali, allora sono generati dallo stesso
z a meno di un fattore reale. Calcolando tutti i c da tutti i generatori z,
i c saranno quindi ripetuti tante volte quanti sono i reali.
Poiche' i reali del gruppo moltiplicativo sono (p-1), allora l'ordine
di C e' (p^2-1)/(p-1) = p+1, dunque :
c^(p+1) = 1 (mod p), i.e., p|F_(p+1).
Chissa' cos'e' sto groppo C... boh!
Crios.

Il problema della non esistenza della radice di 5 si risolve cosi' :
Se 5 e' un non-residuo quadratico mod p, si puo' fare questa
dimostrazione diretta, tipo piccolo teorema di Fermat. Posto r=sqr(5),
F_n = ((1+r)^n-(1-r))^n) / (r*2^n) = 
sviluppo potenza binomio, (n su i) = coeff.binomiale
=(somma{i=0..n}(n su i)r^i - somma{i=0..n}(n su i)(-r)^i))/(r*2^n) =
=(somma{i=0..n}(n su i)(r^i-(-r)^i))/(r*2^n) =
=(somma{i dispari=0..n}(n su i)(2*r^i))/(r*2^n) =
=(somma{i pari=0..n-1}(n su i+1)(2*r*r^i))/(r*2^n) =
=(somma{k=0..parte intera di (n-1)/2} (n su 2k+1) r^(2k))/2^(n-1) =
=(somma{k=0..parte intera di (n-1)/2} (n su 2k+1) 5^k )/2^(n-1),
espressione valida per ogni numero di Fibonacci. Per n=p+1 si ha 
F_(p+1) = (somma{k=0..(p-1)/2} (p+1 su 2k+1) 5^k)/2^p
Per ogni dispari 2k+1 da 3 a p-2 il coefficiente binomiale
(p+1 su 2k+1) e' divisibile per p; allora in modulo p restano solo gli
addendi estremi della somma di sopra:
F_(p+1) = ((p+1 su 1) 5^0 + (p+1 su p) 5^((p-1)/2) ) /2^p = mod p =
(5^0 + 5^((p-1)/2) )/2^p = ( 1 + 5^((p-1)/2) )/2^p
Poiche' 5 e' non-residuo quadratico mod p, 5^((p-1)/2) = -1 (mod p):
F_(p+1) = ( 1 - 1 )/2^p = 0 (mod p). QED

 F_(p+1) = ( 1 - 1 )/2^p = 0 (mod p). QED
D`accordo. 
L`avevo vista, in effetti, ma mi piaceva di piu` un discorso sui gruppi,
in cui n=p+1 viene proprio costruito. 
Con questa via, viceversa, si puo` anche dimostrare che q^((p-1)/2) = -1 (modp)
per q un non residuo, ( j^(p-1)=-1 nella notazione che ho introdotto)
che non mi pare sia un risultato banale, soprattutto per p=1(mod4).