number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, the ''n''th Pisano period, written as '(''n''), is the period 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 cal ...
of
Fibonacci number
In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
s taken
modulo
In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation.
Given two positive numbers and , mo ...
''n'' repeats. Pisano periods are named after Leonardo Pisano, better known as
Fibonacci
Leonardo Bonacci ( – ), commonly known as Fibonacci, was an Italians, Italian mathematician from the Republic of Pisa, considered to be "the most talented Western mathematician of the Middle Ages".
The name he is commonly called, ''Fibonacci ...
. The existence of periodic functions in Fibonacci numbers was noted by
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 ...
:
:
:
For any
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
''n'', the sequence of Fibonacci numbers ''Fi'' taken
modulo
In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation.
Given two positive numbers and , mo ...
''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
In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation.
Given two positive numbers and , mo ...
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
Parity
With the exception of '(2) = 3, the Pisano period '(''n'') is always even.
This follows by observing that '(''n'') is equal to the order of the Fibonacci matrix
:
in the
general linear group
In mathematics, the general linear group of degree n is the set of n\times n invertible matrices, together with the operation of ordinary matrix multiplication. This forms a group, because the product of two invertible matrices is again inve ...
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 ...
2 by 2
matrices
Matrix (: matrices or matrixes) or MATRIX may refer to:
Science and mathematics
* Matrix (mathematics), a rectangular array of numbers, symbols or expressions
* Matrix (logic), part of a formula in prenex normal form
* Matrix (biology), the ...
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 ...
of integers modulo ''n''. Since Q has determinant −1, the determinant of Q'(''n'') is (−1)'(''n''), which is equal to 1 when either ''n'' ≤ 2 or '(''n'') is even.
Pisano periods of composite numbers
If ''m'' and ''n'' are
coprime
In number theory, 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 equiv ...
, then '(''mn'') is the
least common multiple
In arithmetic and number theory, the least common multiple (LCM), lowest common multiple, or smallest common multiple (SCM) of two integers ''a'' and ''b'', usually denoted by , is the smallest positive integer that is divisible by both ''a'' and ...
of '(''m'') and '(''n''). This follows from
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
.
Thus the Pisano periods of composite numbers can be computed by looking at the Pisano periods
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, 1 ...
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
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 "student John Smith is not lazy" is a c ...
would necessarily be a
Wall–Sun–Sun prime
In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.
Definition
Let p be a prime number. When each term in the sequence of Fibona ...
, and conversely every Wall–Sun–Sun prime ''p'' gives a counterexample (set ''k'' = 2).
For ''p'' = 2 and 5, the exact values of the Pisano periods are known. The periods of powers of these prime powers are as follows:
* If ''n'' = 2''k'', then
* if ''n'' = 5''k'', then
From these it follows that if ''n'' = 2·5''k'' then '(''n'') = 6''n''.
Pisano periods of prime numbers
If prime ''p'' is different from 2 and 5, then '(''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 divisibl ...
of ''p''2 − 1. This follows from the modulo ''p'' analogue of
Binet's formula
In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
, which 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 orde ...
of a
root
In vascular plants, the roots are the plant organ, 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 bel ...
of modulo ''p''.
Every ''p'' other than 2 and 5 lie in the residue classes or .
* If , then '(''p'') divides ''p'' − 1.
* If , then '(''p'') divides 2(''p'' + 1).
The former can be proven by observing that if , then the roots of modulo ''p'' belong to (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 divisibl ...
of ''p'' − 1.
To prove the latter, if the roots modulo ''p'' of do not belong to (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 (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
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 that includes finite fields. The endomorphism m ...
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.
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.
If ''n'' is not of the form 2 · 5''r'', then '(''n'') ≤ 4''n''.
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''2 ≡ 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 , and the "rank of apparition" is called the "rank" and denoted .
According to Wall's conjecture, . If has
prime factorization
In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
then .
Generalizations
The Pisano periods of
Lucas number
The Lucas sequence is an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–1891), who studied both that sequence and the closely related Fibonacci sequence. Individual numbers in the Lucas sequence ar ...
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 ...
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 seq ...
algebraic number theory
Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic ob ...
.
Let 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 the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
, 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
coprime
In number theory, 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 equiv ...
, then , by the
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
: 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, and so Thus it suffices to compute Pisano periods for
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, 1 ...
s (Usually, , unless ''p'' is ''k''-
Wall–Sun–Sun prime
In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.
Definition
Let p be a prime number. When each term in the sequence of Fibona ...
, or ''k''-Fibonacci–Wieferich prime, that is, ''p''2 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 2412 divides ''F''3(242).)
For prime numbers ''p'', these can be analyzed by using
Binet's formula
In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
:
: where is the ''k''th metallic mean
:
If ''k''2 + 4 is a
quadratic residue
In number theory, an integer ''q'' is a quadratic residue modulo operation, modulo ''n'' if it is Congruence relation, congruent to a Square number, perfect square modulo ''n''; that is, if there exists an integer ''x'' such that
:x^2\equiv q \pm ...
modulo ''p'' (where ''p'' > 2 and ''p'' does not divide ''k''2 + 4), then and 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 othe ...
, since any power (such as ) has period dividing as this is the
order
Order, ORDER or Orders may refer to:
* A socio-political or established or existing order, e.g. World order, Ancien Regime, Pax Britannica
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
...
of the
group of units
In algebra, a unit or invertible element of a ring is an invertible element for the multiplication of the ring. That is, an element of a ring is a unit if there exists in such that
vu = uv = 1,
where is the multiplicative identity; the ele ...
modulo ''p''.
For ''k'' = 1, this first occurs for ''p'' = 11, where 42 = 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
:
Another example, which shows that the period can properly divide ''p'' − 1, is ''π''1(29) = 14.
If ''k''2 + 4 is not a quadratic residue modulo ''p'', then Binet's formula is instead defined over the
quadratic extension
In mathematics, the term quadratic describes something that pertains to squares, to the operation of squaring, to terms of the second degree, or equations or formulas that involve such terms. ''Quadratus'' is Latin for ''square''.
Mathematics ...