fausto1947 ha scritto:
chiedo scusa per la mia ignoranza ma non capisco la formula che hai scritto, potresti spiegare in termini più pratici?
No, no! Scusami tu, la mia intenzione era solo dire, con fibonacci si può fare anche questo! E non ho spiegato minimamente cose per nulla semplici perché non sono semplici. È normale che non capisci quello che ho scritto, ma siccome sei interessato te lo spiego più nei dettagli. Però se non capisci non preoccuparti mi raccomando perché non sono cose semplici. Cercherò di spiegarmi in modo semplice.
Inoltre mi sono reso conto di aver fatto un typo poiché quella corretta è la seguente:
Dato \(n > 0 \), se
\[ n \not\mid F_{n- \left(\frac{5}{n} \right)} \]
allora \(n \) è composto. Altrimenti è primo oppure uno pseudo-primo di Fibonacci.
Perdonami. Comunque sia:
Hai presente la divisione con resto negli interi? Ovvero \( n = mq + r \) dove \( 0 \leq r \leq n-1 \). Ad esempio \( 72 = 7 \cdot 10 + 2 \). Se due numeri interi \( x,y \) hanno lo stesso resto dopo la divisione per \(q\) li scrivo così \( x \equiv y \mod q \). Cosa vuol dire? Semplicemente che \( x = m_1 q + r_1 \) e \( y = m_2 q + r_2 \) dove \(r_1 = r_2 \), ad esempio \( 72 \equiv 16 \mod 7 \) perché \( 72 = 7 \cdot 10 + 2 \) e \( 16 = 7 \cdot 2 + 2 \), i due resti sono uguali e quindi \(72 \equiv 16 \mod 7 \).
Il simbolo di Legendre è una funzione definita in questo modo. Prendi un numero primo \(p \) che non sia \(2\) e fissalo (vuol dire che non cambi il numero primo una volta scelto). Allora per ogni numero intero \(a\) il simbolo di Legendre è
\[ \left( \frac{a}{p} \right) =\left\{\begin{matrix}
0& \text{ se } a \text{ è un multiplo di } p \\
1& \text{ se esiste un intero } n \text{ tale che } n^2 \equiv a \mod p \\
-1& \text{ altrimenti}
\end{matrix}\right. \]
Ad esempio: Prendi \( p = 5 \) abbiamo che
\( \left( \frac{70}{5} \right) = 0 \) perché \( 70 \) è un multiplo di \( 5 \). Mentre
\( \left( \frac{21}{5} \right) = 1 \) perché \( 4^2 = 16 \equiv 21 \mod 5 \). Mentre
\( \left( \frac{22}{5} \right) = -1 \), infatti puoi verificare che nessun numero elevato al quadrato restituisce resto \(2\) dopo la divisione con \(5\).
Bene, questo è il simbolo di Legendre. Ora Il problema con il simbolo di Legendre è che è definito solo se il numero sotto è un numero primo dispari. Jacobi pertanto ha esteso questo simbolo nel seguente modo.
Sia \( n \) un intero dispari e positivo e consideriamo la sua fattorizzazione in primi \(n = p_1^{k_1} \cdot \ldots \cdot p_r^{k_r} \). E sia \(a \) un intero qualunque, allora definiamo il simbolo di Jacobi (con lo stessa scrittura) in questo modo
\[ \left( \frac{a}{n} \right) = \left( \frac{a}{p_1} \right)^{k_1} \cdot \ldots \cdot \left( \frac{a}{p_r} \right)^{k_r} \]
dove a destra dell'uguale è il simbolo di Legendre. Usiamo la convenzione che se \(n=1 \) allora il prodotto vuoto ci restituisce \( \left( \frac{a}{n} \right) = 1 \).
Ad esempio \( 75 = 5^2 \dot 3 \).
\[ \left( \frac{70}{75} \right) = \left( \frac{70}{5} \right)^2 \left( \frac{70}{3} \right) \]
abbiamo visto prima che \( \left( \frac{70}{5} \right) = 0 \), mentre abbiamo che \( 1^2 = 1 \equiv 70 \mod 3 \) dunque \( \left( \frac{70}{3} \right) = 1 \). Abbiamo dunque
\[ \left( \frac{70}{75} \right) = \left( \frac{70}{5} \right)^2 \left( \frac{70}{3} \right) = 0^2 \cdot 1 = 0 \]
\[ \left( \frac{21}{75} \right) = \left( \frac{21}{5} \right)^2 \left( \frac{21}{3} \right) \]
abbiamo visto prima che \( \left( \frac{21}{5} \right) = 1 \), mentre abbiamo che \( 21 \equiv 0 \mod 3 \) dunque \( \left( \frac{21}{3} \right) = 0 \). Abbiamo dunque
\[ \left( \frac{70}{75} \right) = \left( \frac{70}{5} \right)^2 \left( \frac{70}{3} \right) = 1^2 \cdot 0 = 0 \]
\[ \left( \frac{22}{75} \right) = \left( \frac{22}{5} \right)^2 \left( \frac{22}{3} \right) \]
abbiamo visto prima che \( \left( \frac{22}{5} \right) = - 1 \), mentre abbiamo che \( 1^2 = 1 \equiv 21 \mod 3 \) dunque \( \left( \frac{22}{3} \right) = 1 \). Abbiamo dunque
\[ \left( \frac{22}{75} \right) = \left( \frac{22}{5} \right)^2 \left( \frac{22}{3} \right) = (-1)^2 \cdot 1 = 1 \]
Ora veniamo "alla formula" che ho scritto.
\[ n \not\mid F_{n - \left( \frac{5}{n} \right) } \]
si legge: "\(n\) non divide \( F_{n - \left( \frac{5}{n} \right) } \)". Dove chiaramente con \( F_{k} \) intendo il \(k\)-esimo numero di Fibonacci.
Se questa cosa è verificata (ovvero \(n\) non divide quel numero di Fibonacci) allora certamente \(n\) non è un numero primo. Se lo divide invece può essere primo oppure uno pseudoprimo di Fibonacci (che attualmente non ricordo come sono definiti)
A questo punto potresti pensare di aver bisogno di conoscere la decomposizione in fattori primi di \(n\) per calcolarti \( \left( \frac{5}{n} \right) \), invece la cosa comoda è che ci sono alcune proprietà del simbolo di Jacobi che ti permettono di calcolarlo senza conoscere la decomposizione in fattori primi di \(n\). Ti faccio un esempio, con numeri piccoli.
Ad esempio vale la legge della reciprocità quadratica anche per il simbolo di Jacobi. Ovvero dati due numeri interi positivi \(n,m\) dispari e coprimi tra loro (che vuol dire che non hanno divisori in comune) allora
\[ \left( \frac{n}{m} \right) \left( \frac{m}{n} \right) = (-1)^{\frac{n-1}{2} \cdot \frac{m-1}{2} } \]
Inoltre le proprietà utili al calcolo sono le seguenti:
1) Se \( a \equiv b \mod n \) allora
\[ \left( \frac{a}{n} \right) = \left( \frac{b}{n} \right) \]
2) \[ \left( \frac{ab}{n} \right) = \left( \frac{a}{n} \right)\left( \frac{b}{n} \right) \]
Ti faccio un paio di esempi con dei numeri piccoli per il test di Primalità di Fibonacci.
Interessiamoci solo agli \(n\) che non sono multipli di \(5\), perché chiaramente altrimenti non è primo e a noi interessa capire se \(n\) può essere un "probabile" numero primo. Allora siccome \(5\) è primo abbiamo che \(n \) e \(5\) sono coprimi siccome \(5 \not\mid n \) (che si legge 5 non divide \(n\)).
Prendiamo \(n=61 \)
\(61 \) e \(5\) sono coprimi, applichiamo quindi la reciprocità quadratica e abbiamo che
\[ \left( \frac{5}{61} \right)\left( \frac{61}{5} \right) = (-1)^{\frac{61-1}{2} \cdot \frac{5-1}{2} } = (-1)^{30 \cdot 2} = 1 \]
Pertanto abbiamo
\[ \left( \frac{5}{61} \right) =\left( \frac{61}{5} \right) \]
infatti o sono entrambi \(-1 \) oppure entrambi \(1\) siccome il loro prodotto è uguale a \(1\).
Ora applichiamo la proprietà 1) per dire che \(61 \equiv 1 \mod 5 \) e abbiamo che
\[ \left( \frac{5}{61} \right) =\left( \frac{61}{5} \right) = \left( \frac{1}{5} \right) \]
ora applichiamo la proprietà 2) e notiamo che
\[ \left( \frac{1}{5} \right) = \left( \frac{1^2}{5} \right) = \left( \frac{1}{5} \right)^2 = 1 \]
dunque abbiamo che
\[ \left( \frac{5}{61} \right) =\left( \frac{61}{5} \right) = \left( \frac{1}{5} \right) = 1 \]
Dunque dobbiamo verificare che
\[ 61 \mid F_{61-1} \]
Abbiamo che \(F_{60} = 1548008755920 \) e puoi verificare che \( 61 \mid 1548008755920\) Infatti abbiamo che
\[ 1548008755920 = 25377192720 \cdot 61 \]
quello che ci dice il test è che \(61\) può essere primo oppure uno pseudoprimo di Fibonacci. Nel nostro caso specifico \(61\) è primo ma non puoi concluderlo dal test.
Prendiamo ad esempio \(57\) e vogliamo capire se è primo oppure no. Ragioniamo in modo analogo.
Reciprocità:
\[ \left( \frac{5}{57} \right) \left( \frac{57}{5} \right) = (-1)^{\frac{57-1}{2} \cdot \frac{5-1}{2} } = 1 \]
Dunque
\[ \left( \frac{5}{57} \right) = \left( \frac{57}{5} \right) \]
applicando la regola 1) abbiamo
\[ \left( \frac{5}{57} \right) = \left( \frac{57}{5} \right) = \left( \frac{2}{5} \right) \]
Come detto in precedenza questo numero è facile da calcolare perché nessun numero elevato alla seconda restituisce resto \(2\) dopo la divisione per \(5\). Pertanto sappiamo che \(\left( \frac{2}{5} \right)=-1\) e abbiamo
\[ \left( \frac{5}{57} \right) =-1 \]
Quindi dobbiamo verificare se
\[ 57 \mid F_{57 - (-1)} = F_{58} \]
Abbiamo che \(F_{58} = 591286729879 \) e si può verificare facilmente che \( 57 \) non divide \( 591286729879 \) dunque \(57\) non è primo.
)
