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 ...

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 ...

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 ...

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 ...

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 ...

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 (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 ''F_i'' 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. PisanoPeriod n3

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 :

\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 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 ...

\text_2(\mathbb_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 ...

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 ...

\mathbb_n

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

\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 "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

\pi(n) = 3 \cdot 2^ = \frac2

* if ''n'' = 5^''k'', then

\pi(n) = 4 \cdot 5^k = 4n

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''² − 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

p \equiv \pm 1\ (\mathrm\ 10)

or

p \equiv \pm 3\ (\mathrm\ 10)

. * If

p \equiv \pm 1\ (\mathrm\ 10)

, then '(''p'') divides ''p'' − 1. * If

p \equiv \pm 3\ (\mathrm\ 10)

, then '(''p'') divides 2(''p'' + 1). The former can be proven by observing that if

p \equiv \pm 1\ (\mathrm\ 10)

, then the roots of modulo ''p'' 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 divisibl ...

of ''p'' − 1. To prove the latter, if

p \equiv \pm 3\ (\mathrm\ 10),

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 (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...

\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 that 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. 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''.

Tables

The first twelve Pisano periods and their cycles (with spaces before the zeros for readability) areGraph 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.
/ref> (using X and E 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 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 ...

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 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 ...

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 numbers (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 seq ...

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.

Number theory

Pisano periods can be analyzed using

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

\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 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

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

, 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,

\pi_1(3)=8

and

\pi_1(4)=6,

so

\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

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^n.

(Usually,

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

, 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''² 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

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 ...

: :

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

where

\varphi_k

is the ''k''th metallic mean :

\varphi_k = \frac.

If ''k''² + 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''² + 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 othe ...

\phi(p)=p-1

, since any power (such as

\varphi_k^n

) has period dividing

\phi(p),

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 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, 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 ...

field

(\mathbb/p)

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

/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 ze ...

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 The University of Nottingham is a public research university in Nottingham, England. It was founded as University College Nottingham in 1881, and was granted a royal charter in 1948. Nottingham's main campus (University Park Campus, Nottingh ...

Fibonacci numbers Modular arithmetic