Fibonacci

Alcuni studenti mi hanno segnalato un libro in cui sono inclusi alcuni “giochi” che si trovano dei libri di Fibonacci. In particolare “Indovina il numero minore di 105”. In questo caso una persona pensa un numero n minore di 105 e comunica i tre resti delle divisioni per 3, 5 e 7, rispettivamente r_1,r_2 e r_3. Il numero di partenza si ottiene calcolando 70 r_1+ 21 r_2 + 15 r_3 meno eventuali multipli di 105, se necessario.

Dal punto di vista matematico, questo è la soluzione di un sistema di equazioni modulari

n=a_1 (mod\ b_1)n=a_r (mod\ b_r)

Per essere sicuri che ci sia soluzione per ogni scelta degli a_i dobbiamo avere tutti i b_i coprimi a due a due. In questo caso una soluzione è

n=\sum_i a_i c_i (c_i)^{-1}_{b_i}

dove c_i=\frac{b_1 \cdots b_r}{b_i} e (c_i)^{-1}_{b_i} è l’inverso calcolato modulo b_i.

Nel caso di sopra, abbiamo c_1=35c_2=21c_3=15 e gli inversi sono 2, 1 e 1, che corrisponde con la formula di Fibonacci.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.

Time limit is exhausted. Please reload CAPTCHA.