number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...

, the ''n''th Pisano period, written as '(''n''), is the

period Period may refer to: Common uses * Era, a length or span of time * Full stop (or period), a punctuation mark Arts, entertainment, and media * Period (music), a concept in musical composition * Periodic sentence (or rhetorical period), a concept ...

with which the

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...

Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...

s taken modulo ''n'' repeats. Pisano periods are named after Leonardo Pisano, better known as

Fibonacci Fibonacci (; also , ; – ), also known as Leonardo Bonacci, Leonardo of Pisa, or Leonardo Bigollo Pisano ('Leonardo the Traveller from Pisa'), was an Italian mathematician from the Republic of Pisa, considered to be "the most talented Wester ...

. The existence of periodic functions in Fibonacci numbers was noted by

Joseph Louis Lagrange Joseph-Louis Lagrange (born Giuseppe Luigi Lagrangia

Definition

The Fibonacci numbers are the numbers in the

integer sequence In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers. An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...

: :0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, ... defined by the

recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...

F_0 = 0

F_1 = 1

F_i = F_ + F_.

For any

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

''n'', the sequence of Fibonacci numbers ''F_i'' taken modulo ''n'' is periodic. The Pisano period, denoted '(''n''), is the length of the period of this sequence. For example, the sequence of Fibonacci numbers modulo 3 begins: :0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ... This sequence has period 8, so '(3) = 8.

Properties

With the exception of '(2) = 3, the Pisano period '(''n'') is always even. A simple proof of this can be given by observing that '(''n'') is equal to the order of the Fibonacci matrix :

\mathbf Q = \begin 1 & 1\\1 & 0 \end

in the

general linear group In mathematics, the general linear group of degree ''n'' is the set of invertible matrices, together with the operation of ordinary matrix multiplication. This forms a group, because the product of two invertible matrices is again invertible, ...

''GL''₂(ℤ_''n'') of

invertible In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers. Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...

2 by 2

matrices Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

in the

finite ring In mathematics, more specifically abstract algebra, a finite ring is a ring that has a finite number of elements. Every finite field is an example of a finite ring, and the additive part of every finite ring is an example of an abelian finite grou ...

ℤ_''n'' of integers modulo ''n''. Since Q has determinant −1, the determinant of Q^'(''n'') is (−1)^'(''n''), and since this must equal 1 in ℤ_''n'', either ''n'' ≤ 2 or '(''n'') is even. If ''m'' and ''n'' are

coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...

, then '(''mn'') is the

least common multiple In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...

of '(''m'') and '(''n''), by the Chinese remainder theorem. For example, '(3) = 8 and '(4) = 6 imply '(12) = 24. Thus the study of Pisano periods may be reduced to that of Pisano periods of

prime power In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number. For example: , and are prime powers, while , and are not. The sequence of prime powers begins: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...

s ''q'' = ''p''^''k'', for ''k'' ≥ 1. If ''p'' is

prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

, '(''p''^''k'') divides ''p''^''k''–1 '(''p''). It is unknown if

\pi(p^k) = p^\pi(p)

for every prime ''p'' and integer ''k'' > 1. Any prime ''p'' providing a

counterexample A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "John Smith is not a lazy student" is a ...

would necessarily be a Wall–Sun–Sun prime, and conversely every Wall–Sun–Sun prime ''p'' gives a counterexample (set ''k'' = 2). So the study of Pisano periods may be further reduced to that of Pisano periods of primes. In this regard, two primes are anomalous. The prime 2 has an

odd Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric. Odd may also refer to: Acronym * ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...

Pisano period, and the prime 5 has period that is relatively much larger than the Pisano period of any other prime. The periods of powers of these primes are as follows: * If ''n'' = 2^''k'', then '(''n'') = 3·2^''k''–1 = = . * if ''n'' = 5^''k'', then '(''n'') = 20·5^''k''–1 = = 4''n''. From these it follows that if ''n'' = 2·5^''k'' then '(''n'') = 6''n''. The remaining primes all lie in the residue classes

p \equiv \pm 1 \pmod

p \equiv \pm 3 \pmod

. If ''p'' is a prime different from 2 and 5, then the modulo ''p'' analogue of

Binet's formula In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...

implies that '(''p'') is the

multiplicative order In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n. In other words, the multiplicative order ...

of a

root In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the su ...

of modulo ''p''. If

p \equiv \pm 1 \pmod

, these roots belong to

\mathbb_ = \mathbb/p\mathbb

(by

quadratic reciprocity In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard st ...

). Thus their order, '(''p'') is a

divisor In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...

of ''p'' − 1. For example, '(11) = 11 − 1 = 10 and '(29) = (29 − 1)/2 = 14. If

p \equiv \pm 3 \pmod ,

the roots modulo ''p'' of do not belong to

\mathbb_

(by quadratic reciprocity again), and belong to the

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...

\mathbb_(x^2 - x - 1).

As the

Frobenius automorphism In commutative algebra and field theory, the Frobenius endomorphism (after Ferdinand Georg Frobenius) is a special endomorphism of commutative rings with prime characteristic , an important class which includes finite fields. The endomorphism m ...

x \mapsto x^p

exchanges these roots, it follows that, denoting them by ''r'' and ''s'', we have ''r''^''p'' = ''s'', and thus ''r''^''p''+1 = –1. That is ''r''^2(''p''+1) = 1, and the Pisano period, which is the order of ''r'', is the quotient of 2(''p''+1) by an odd divisor. This quotient is always a multiple of 4. The first examples of such a ''p'', for which '(''p'') is smaller than 2(''p''+1), are '(47) = 2(47 + 1)/3 = 32, '(107) = 2(107 + 1)/3 = 72 and '(113) = 2(113 + 1)/3 = 76. ( See the table below) It follows from above results, that if ''n'' = ''p''^''k'' is an odd prime power such that '(''n'') > ''n'', then '(''n'')/4 is an integer that is not greater than ''n''. The multiplicative property of Pisano periods imply thus that :'(''n'') ≤ 6''n'', with equality if and only if ''n'' = 2 · 5^''r'', for ''r'' ≥ 1. The first examples are '(10) = 60 and '(50) = 300. If ''n'' is not of the form 2 · 5^''r'', then '(''n'') ≤ 4''n''.

Tables

The first twelve Pisano periods and their cycles (with spaces before the zeros for readability) are Graph of the cycles modulo 1 to 24. Each row of the image represents a different modulo base ''n'', from 1 at the bottom to 24 at the top. The columns represent the Fibonacci numbers mod ''n'', from ''F''(0) mod ''n'' at the left to ''F''(59) mod ''n'' on the right. In each cell, the brightness indicates the value of the residual, from dark for 0 to near-white for ''n''−1. Blue squares on the left represent the first period; the number of blue squares is the Pisano number. (using hexadecimal cyphers A and B for ten and eleven, respectively): The first 144 Pisano periods are shown in the following table:

Pisano periods of Fibonacci numbers

If ''n'' = ''F''(2''k'') (''k'' ≥ 2), then π(''n'') = 4''k''; if ''n'' = ''F''(2''k'' + 1) (''k'' ≥ 2), then π(''n'') = 8''k'' + 4. That is, if the modulo base is a Fibonacci number (≥ 3) with an even index, the period is twice the index and the cycle has two zeros. If the base is a Fibonacci number (≥ 5) with an odd index, the period is four times the index and the cycle has four zeros.

Pisano periods of Lucas numbers

If ''n'' = ''L''(2''k'') (''k'' ≥ 1), then π(''n'') = 8''k''; if ''n'' = ''L''(2''k'' + 1) (''k'' ≥ 1), then π(''n'') = 4''k'' + 2. That is, if the modulo base is a Lucas number (≥ 3) with an even index, the period is four times the index. If the base is a Lucas number (≥ 4) with an odd index, the period is twice the index. For even ''k'', the cycle has two zeros. For odd ''k'', the cycle has only one zero, and the second half of the cycle, which is of course equal to the part on the left of 0, consists of alternatingly numbers ''F''(2''m'' + 1) and ''n'' − ''F''(2''m''), with ''m'' decreasing.

Number of zeros in the cycle

The number of occurrences of 0 per cycle is 1, 2, or 4. Let ''p'' be the number after the first 0 after the combination 0, 1. Let the distance between the 0s be ''q''. *There is one 0 in a cycle, obviously, if ''p'' = 1. This is only possible if ''q'' is even or ''n'' is 1 or 2. *Otherwise there are two 0s in a cycle if ''p''² ≡ 1. This is only possible if ''q'' is even. *Otherwise there are four 0s in a cycle. This is the case if ''q'' is odd and ''n'' is not 1 or 2. For generalized Fibonacci sequences (satisfying the same recurrence relation, but with other initial values, e.g. the Lucas numbers) the number of occurrences of 0 per cycle is 0, 1, 2, or 4. The ratio of the Pisano period of ''n'' and the number of zeros modulo ''n'' in the cycle gives the ''rank of apparition'' or ''Fibonacci entry point'' of ''n''. That is, smallest index ''k'' such that ''n'' divides ''F''(''k''). They are: :1, 3, 4, 6, 5, 12, 8, 6, 12, 15, 10, 12, 7, 24, 20, 12, 9, 12, 18, 30, 8, 30, 24, 12, 25, 21, 36, 24, 14, 60, 30, 24, 20, 9, 40, 12, 19, 18, 28, 30, 20, 24, 44, 30, 60, 24, 16, 12, ... In Renault's paper the number of zeros is called the "order" of ''F'' mod ''m'', denoted

\omega(m)

, and the "rank of apparition" is called the "rank" and denoted

\alpha(m)

. According to Wall's conjecture,

\alpha(p^e) = p^ \alpha(p)

. If

m

has prime factorization

m = p_1^ p_2^ \dots p_n^

then

\alpha(m) = \operatorname(\alpha(p_1^), \alpha(p_2^), \dots, \alpha(p_n^))

Generalizations

The Pisano periods of

Lucas number The Lucas numbers or Lucas series are an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–1891), who studied both that sequence and the closely related Fibonacci numbers. Lucas numbers and Fibonacci n ...

s are :1, 3, 8, 6, 4, 24, 16, 12, 24, 12, 10, 24, 28, 48, 8, 24, 36, 24, 18, 12, 16, 30, 48, 24, 20, 84, 72, 48, 14, 24, 30, 48, 40, 36, 16, 24, 76, 18, 56, 12, 40, 48, 88, 30, 24, 48, 32, ... The Pisano periods of

Pell number In mathematics, the Pell numbers are an infinite sequence of integers, known since ancient times, that comprise the denominators of the closest rational approximations to the square root of 2. This sequence of approximations begins , , , , an ...

s (or 2-Fibonacci numbers) are :1, 2, 8, 4, 12, 8, 6, 8, 24, 12, 24, 8, 28, 6, 24, 16, 16, 24, 40, 12, 24, 24, 22, 8, 60, 28, 72, 12, 20, 24, 30, 32, 24, 16, 12, 24, 76, 40, 56, 24, 10, 24, 88, 24, 24, 22, 46, 16, ... The Pisano periods of 3-Fibonacci numbers are :1, 3, 2, 6, 12, 6, 16, 12, 6, 12, 8, 6, 52, 48, 12, 24, 16, 6, 40, 12, 16, 24, 22, 12, 60, 156, 18, 48, 28, 12, 64, 48, 8, 48, 48, 6, 76, 120, 52, 12, 28, 48, 42, 24, 12, 66, 96, 24, ... The Pisano periods of

Jacobsthal number In mathematics, the Jacobsthal numbers are an integer sequence named after the German mathematician Ernst Jacobsthal. Like the related Fibonacci numbers, they are a specific type of Lucas sequence U_n(P,Q) for which ''P'' = 1, and ''Q''& ...

s (or (1,2)-Fibonacci numbers) are :1, 1, 6, 2, 4, 6, 6, 2, 18, 4, 10, 6, 12, 6, 12, 2, 8, 18, 18, 4, 6, 10, 22, 6, 20, 12, 54, 6, 28, 12, 10, 2, 30, 8, 12, 18, 36, 18, 12, 4, 20, 6, 14, 10, 36, 22, 46, 6, ... The Pisano periods of (1,3)-Fibonacci numbers are :1, 3, 1, 6, 24, 3, 24, 6, 3, 24, 120, 6, 156, 24, 24, 12, 16, 3, 90, 24, 24, 120, 22, 6, 120, 156, 9, 24, 28, 24, 240, 24, 120, 48, 24, 6, 171, 90, 156, 24, 336, 24, 42, 120, 24, 66, 736, 12, ... The Pisano periods of

Tribonacci number In mathematics, the Fibonacci numbers form a sequence defined recursively by: :F_n = \begin 0 & n = 0 \\ 1 & n = 1 \\ F_ + F_ & n > 1 \end That is, after two starting values, each number is the sum of the two preceding numbers. The Fibonacci seque ...

s (or 3-step Fibonacci numbers) are :1, 4, 13, 8, 31, 52, 48, 16, 39, 124, 110, 104, 168, 48, 403, 32, 96, 156, 360, 248, 624, 220, 553, 208, 155, 168, 117, 48, 140, 1612, 331, 64, 1430, 96, 1488, 312, 469, 360, 2184, 496, 560, 624, 308, 440, 1209, 2212, 46, 416, ... The Pisano periods of Tetranacci numbers (or 4-step Fibonacci numbers) are :1, 5, 26, 10, 312, 130, 342, 20, 78, 1560, 120, 130, 84, 1710, 312, 40, 4912, 390, 6858, 1560, 4446, 120, 12166, 260, 1560, 420, 234, 1710, 280, 1560, 61568, 80, 1560, 24560, 17784, 390, 1368, 34290, 1092, 1560, 240, 22230, 162800, 120, 312, 60830, 103822, 520, ... See also

generalizations of Fibonacci numbers In mathematics, the Fibonacci numbers form a sequence defined recursively by: :F_n = \begin 0 & n = 0 \\ 1 & n = 1 \\ F_ + F_ & n > 1 \end That is, after two starting values, each number is the sum of the two preceding numbers. The Fibonacci seque ...

Number theory

Pisano periods can be analyzed using algebraic number theory. Let

\pi_k(n)

be the ''n''-th Pisano period of the ''k''-Fibonacci sequence ''F''_''k''(''n'') (''k'' can be any

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...

, these sequences are defined as ''F''_''k''(0) = 0, ''F''_''k''(1) = 1, and for any natural number ''n'' > 1, ''F''_''k''(''n'') = ''kF''_''k''(''n''−1) + ''F''_''k''(''n''−2)). If ''m'' and ''n'' are

, then

\pi_k(m\cdot n) = \mathrm(\pi_k(m),\pi_k(n))

, by the Chinese remainder theorem: two numbers are congruent modulo ''mn'' if and only if they are congruent modulo ''m'' and modulo ''n'', assuming these latter are coprime. For example,

\pi_1(3)=8

and

\pi_1(4)=6,

\pi_1(12=3\cdot 4) = \mathrm(\pi_1(3),\pi_1(4))= \mathrm(8,6)=24.

Thus it suffices to compute Pisano periods for

q=p^n.

(Usually,

\pi_k(p^n) = p^\cdot \pi_k(p)

, unless ''p'' is ''k''- Wall–Sun–Sun prime, or ''k''-Fibonacci–Wieferich prime, that is, ''p''² divides ''F''_''k''(''p'' − 1) or ''F''_''k''(''p'' + 1), where ''F''_''k'' is the ''k''-Fibonacci sequence, for example, 241 is a 3-Wall–Sun–Sun prime, since 241² divides ''F''₃(242).) For prime numbers ''p'', these can be analyzed by using

: :

F_k\left(n\right) = =,\,

where

\varphi_k

is the ''k''th

metallic mean The metallic means (also ratios or constants) of the successive natural numbers are the continued fractions: n + \cfrac = ;n,n,n,n,\dots= \frac. The golden ratio (1.618...) is the metallic mean between 1 and 2, while the silver ratio (2.414 ...

\varphi_k = \frac.

If ''k''² + 4 is a quadratic residue modulo ''p'' (where ''p'' > 2 and ''p'' does not divide ''k''² + 4), then

\sqrt, 1/2,

and

k/\sqrt

can be expressed as integers modulo ''p'', and thus Binet's formula can be expressed over integers modulo ''p'', and thus the Pisano period divides the

totient In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ...

\phi(p)=p-1

, since any power (such as

\varphi_k^n

) has period dividing

\phi(p),

as this is the order of the group of units modulo ''p''. For ''k'' = 1, this first occurs for ''p'' = 11, where 4² = 16 ≡ 5 (mod 11) and 2 · 6 = 12 ≡ 1 (mod 11) and 4 · 3 = 12 ≡ 1 (mod 11) so 4 = , 6 = 1/2 and 1/ = 3, yielding ''φ'' = (1 + 4) · 6 = 30 ≡ 8 (mod 11) and the congruence :

F_1\left(n\right) \equiv 3\cdot \left(8^n - 4^n\right) \pmod.

Another example, which shows that the period can properly divide ''p'' − 1, is ''π''₁(29) = 14. If ''k''² + 4 is not a quadratic residue modulo ''p'', then Binet's formula is instead defined over the

quadratic extension In mathematics, particularly in algebra, a field extension is a pair of fields E\subseteq F, such that the operations of ''E'' are those of ''F'' restricted to ''E''. In this case, ''F'' is an extension field of ''E'' and ''E'' is a subfield of ...

field

(\mathbb/p)

sqrt In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or  ⋅ ) is . For example, 4 and −4 are square roots of 16, because . ...

/math>, which has ''p''² elements and whose group of units thus has order ''p''² − 1, and thus the Pisano period divides ''p''² − 1. For example, for ''p'' = 3 one has ''π''₁(3) = 8 which equals 3² − 1 = 8; for ''p'' = 7, one has ''π''₁(7) = 16, which properly divides 7² − 1 = 48. This analysis fails for ''p'' = 2 and ''p'' is a divisor of the squarefree part of ''k''² + 4, since in these cases are

zero divisor In abstract algebra, an element of a ring is called a left zero divisor if there exists a nonzero in such that , or equivalently if the map from to that sends to is not injective. Similarly, an element of a ring is called a right zer ...

s, so one must be careful in interpreting 1/2 or

\sqrt

. For ''p'' = 2, is congruent to 1 mod 2 (for ''k'' odd), but the Pisano period is not ''p'' − 1 = 1, but rather 3 (in fact, this is also 3 for even ''k''). For ''p'' divides the squarefree part of ''k''² + 4, the Pisano period is ''π''_''k''(''k''² + 4) = ''p''² − ''p'' = ''p''(''p'' − 1), which does not divide ''p'' − 1 or ''p''² − 1.

Fibonacci integer sequences modulo ''n''

One can consider Fibonacci integer sequences and take them modulo ''n'', or put differently, consider Fibonacci sequences in the ring Z/''n''Z. The period is a divisor of π(''n''). The number of occurrences of 0 per cycle is 0, 1, 2, or 4. If ''n'' is not a prime the cycles include those that are multiples of the cycles for the divisors. For example, for ''n'' = 10 the extra cycles include those for ''n'' = 2 multiplied by 5, and for ''n'' = 5 multiplied by 2. Table of the extra cycles: (the original Fibonacci cycles are excluded) (using X and E for ten and eleven, respectively) Number of Fibonacci integer cycles mod ''n'' are: :1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 14, 10, 7, 8, 12, 16, 9, 16, 22, 16, 29, 28, 12, 30, 13, 14, 14, 22, 63, 24, 34, 32, 39, 34, 30, 58, 19, 86, 32, 52, 43, 58, 22, 78, 39, 46, 70, 102, ...

Notes

References

* * * * * * * * * *

External links

The Fibonacci sequence modulo mFibonacci sequence starts with q, r modulo m
* *{{YouTube, Nu-lW-Ifyec, Fibonacci Mystery - Numberphile, a video with Dr. James Grime and the

University of Nottingham , mottoeng = A city is built on wisdom , established = 1798 – teacher training college1881 – University College Nottingham1948 – university status , type = Public , chancellor ...

Fibonacci numbers Modular arithmetic