Nel seguente appunto presenteremo un approfondimento relativo alla successione di Fibonacci. Questo approfondimento è strettamente correlato all'aritmetica modulare.
Anche detta aritmetica dell'orologio, questa branca della matematica trova applicazione in molti ambiti della vita quotidiana, come ad esempio la crittografia. Grazie ad essa, pur non conoscendo il valore esatto di numeri piuttosto grandi, è possibile determinare il resto che si ottiene dividendo tali numeri grandi per un certo intero
Operazione modulo e sequenza di Fibonacci
L'operazione moduloricorre spesso anche in informatica ed è rappresentata (spesso) dalla sintassi a % b.
Questa operazione restituisce il resto che si ottiene dividendo
se quando sono divisi per
,
Equivalentemente, se
diviso per
dà
come resto, allora
.
Ad esempio, potremo dire che
oppure che
.
Queste relazioni sono di importanza notevole in aritmetica modulare e sono chiamate congruenze modulo
Approfondiamo ora alcuni esercizi con la successione di Fibonacci che consistono nella determinazione del resto che si ha dividendo un qualsiasi numero della successione per un certo numero a nostra scelta. Ricordiamo che la successione è definita ricorsivamente, cioè ogni numero è la somma degli altri due precedenti.
Per approfondimenti sull'aritmetica modulare vedi anche qua
Esercizio 1
Detto
per ogni
, calcolare il resto che si ottiene
per 3.
Scriviamo quindi i valori di
modulo
, anziché ragionare con numeri molto grandi. Sommiamo i resti della divisione per 3, per ogni n-esimo numero, degli altri due precedenti. Difatti, una proprietà molto importante dell'aritmetica modulare è la seguente:
Non ci importa quindi quanto valga
; pertanto sommeremo solamente i resti. Siamo infatti tutti d'accordo sul fatto che lavorando solo sui resti nella divisione per
Abbiamo:
.
Inoltre avremo che
. Quindi, anziché scrivere il valore effettivo di
, scriveremo il suo resto nella divisone per
in poi.
Quindi:
.
Tuttavia, già da
in poi, notiamo che la successione è periodica, cioè i termini tendono a ripetersi. Supponiamo quindi di suddividere la successione di Fibonacci in blocchi di lunghezza
, tutti identici. Cerchiamo di scoprire qual è la posizione di
nel suo blocco.
Poiché 2018 diviso per 8 dà resto 2, la posizione è
, allora il resto della divisione di
per
è lo stesso di
, ovvero
.
Esercizio 2
Calcolare il resto che si ottiene dividendo per
il 3182-esimo numero di Fibonacci.
Bisogna ora ragionare modulo
.
Si ha quindi:
Stavolta la successione si ripete con periodo
. Reiteriamo lo stesso ragionamento di prima anche per questo esercizio: essendo la successione dotata di periodo
, suddividiamola in blocchi. Si avrà quindi che ogni blocco è uguale all'altro e ha lunghezza
, ma per trovare la posizione equivalente di
devo effettuare una divisone e prenderne il resto.
Poiché
diviso per
dà resto
, la posizione relativa all'interno del blocco sarà pari a
. In definitiva, il resto cercato equivale a
, ossia lo stesso resto che si ottiene quando è
ad essere diviso per
.
Per approfondimenti sulla successione di Fibonacci, vedi anche qua
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
