The Pisano Period

I came upon the concept of Pisano periods in a YouTube video titled Alien Primes: The Wall–Sun–Sun Primes, uploaded on August 15th 2022. As explained in Wikipedia:

In number theory, the \(n\)-th Pisano period, written as \( \pi(n) \), is the period with which the sequence of Fibonacci numbers taken modulo \(n\) repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774.

Now the Fibonacci sequence begins: 

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

If we consider the Fibonacci numbers modulo 10 we get a sequence with a period of 60 and thus \( \pi(10) = 60\):

0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1, ... (permalink)

The Fibonacci numbers modulo 7 have a period of 16 and thus \( \pi(7) = 16\):

0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1, ... (permalink)

Figure 1 shows the Fibonacci numbers modulo 4:

Figure 1: pisano(4) or \( \pi \)(4)=6

Figure 2 shows the first 144 Pisano periods. All are even except for \( \pi(3)=3\).

Figure 2: Source

Even with quite a large modulo like 999, the sequence eventually repeats after 1368 steps:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 598, 586, 185, 771, 956, 728, 685, 414, 100, 514, 614, 129, 743, 872, 616, 489, 106, 595, 701, 297, 998, 296, 295, 591, 886, 478, 365, 843, 209, 53, 262, 315, 577, 892, 470, 363, 833, 197, 31, 228, 259, 487, 746, 234, 980, 215, 196, 411, 607, 19, 626, 645, 272, 917, 190, 108, 298, 406, 704, 111, 815, 926, 742, 669, 412, 82, 494, 576, 71, 647, 718, 366, 85, 451, 536, 987, 524, 512, 37, 549, 586, 136, 722, 858, 581, 440, 22, 462, 484, 946, 431, 378, 809, 188, 997, 186, 184, 370, 554, 924, 479, 404, 883, 288, 172, 460, 632, 93, 725, 818, 544, 363, 907, 271, 179, 450, 629, 80, 709, 789, 499, 289, 788, 78, 866, 944, 811, 756, 568, 325, 893, 219, 113, 332, 445, 777, 223, 1, 224, 225, 449, 674, 124, 798, 922, 721, 644, 366, 11, 377, 388, 765, 154, 919, 74, 993, 68, 62, 130, 192, 322, 514, 836, 351, 188, 539, 727, 267, 994, 262, 257, 519, 776, 296, 73, 369, 442, 811, 254, 66, 320, 386, 706, 93, 799, 892, 692, 585, 278, 863, 142, 6, 148, 154, 302, 456, 758, 215, 973, 189, 163, 352, 515, 867, 383, 251, 634, 885, 520, 406, 926, 333, 260, 593, 853, 447, 301, 748, 50, 798, 848, 647, 496, 144, 640, 784, 425, 210, 635, 845, 481, 327, 808, 136, 944, 81, 26, 107, 133, 240, 373, 613, 986, 600, 587, 188, 775, 963, 739, 703, 443, 147, 590, 737, 328, 66, 394, 460, 854, 315, 170, 485, 655, 141, 796, 937, 734, 672, 407, 80, 487, 567, 55, 622, 677, 300, 977, 278, 256, 534, 790, 325, 116, 441, 557, 998, 556, 555, 112, 667, 779, 447, 227, 674, 901, 576, 478, 55, 533, 588, 122, 710, 832, 543, 376, 919, 296, 216, 512, 728, 241, 969, 211, 181, 392, 573, 965, 539, 505, 45, 550, 595, 146, 741, 887, 629, 517, 147, 664, 811, 476, 288, 764, 53, 817, 870, 688, 559, 248, 807, 56, 863, 919, 783, 703, 487, 191, 678, 869, 548, 418, 966, 385, 352, 737, 90, 827, 917, 745, 663, 409, 73, 482, 555, 38, 593, 631, 225, 856, 82, 938, 21, 959, 980, 940, 921, 862, 784, 647, 432, 80, 512, 592, 105, 697, 802, 500, 303, 803, 107, 910, 18, 928, 946, 875, 822, 698, 521, 220, 741, 961, 703, 665, 369, 35, 404, 439, 843, 283, 127, 410, 537, 947, 485, 433, 918, 352, 271, 623, 894, 518, 413, 931, 345, 277, 622, 899, 522, 422, 944, 367, 312, 679, 991, 671, 663, 335, 998, 334, 333, 667, 1, 668, 669, 338, 8, 346, 354, 700, 55, 755, 810, 566, 377, 943, 321, 265, 586, 851, 438, 290, 728, 19, 747, 766, 514, 281, 795, 77, 872, 949, 822, 772, 595, 368, 963, 332, 296, 628, 924, 553, 478, 32, 510, 542, 53, 595, 648, 244, 892, 137, 30, 167, 197, 364, 561, 925, 487, 413, 900, 314, 215, 529, 744, 274, 19, 293, 312, 605, 917, 523, 441, 964, 406, 371, 777, 149, 926, 76, 3, 79, 82, 161, 243, 404, 647, 52, 699, 751, 451, 203, 654, 857, 512, 370, 882, 253, 136, 389, 525, 914, 440, 355, 795, 151, 946, 98, 45, 143, 188, 331, 519, 850, 370, 221, 591, 812, 404, 217, 621, 838, 460, 299, 759, 59, 818, 877, 696, 574, 271, 845, 117, 962, 80, 43, 123, 166, 289, 455, 744, 200, 944, 145, 90, 235, 325, 560, 885, 446, 332, 778, 111, 889, 1, 890, 891, 782, 674, 457, 132, 589, 721, 311, 33, 344, 377, 721, 99, 820, 919, 740, 660, 401, 62, 463, 525, 988, 514, 503, 18, 521, 539, 61, 600, 661, 262, 923, 186, 110, 296, 406, 702, 109, 811, 920, 732, 653, 386, 40, 426, 466, 892, 359, 252, 611, 863, 475, 339, 814, 154, 968, 123, 92, 215, 307, 522, 829, 352, 182, 534, 716, 251, 967, 219, 187, 406, 593, 0, 593, 593, 187, 780, 967, 748, 716, 465, 182, 647, 829, 477, 307, 784, 92, 876, 968, 845, 814, 660, 475, 136, 611, 747, 359, 107, 466, 573, 40, 613, 653, 267, 920, 188, 109, 297, 406, 703, 110, 813, 923, 737, 661, 399, 61, 460, 521, 981, 503, 485, 988, 474, 463, 937, 401, 339, 740, 80, 820, 900, 721, 622, 344, 966, 311, 278, 589, 867, 457, 325, 782, 108, 890, 998, 889, 888, 778, 667, 446, 114, 560, 674, 235, 909, 145, 55, 200, 255, 455, 710, 166, 876, 43, 919, 962, 882, 845, 728, 574, 303, 877, 181, 59, 240, 299, 539, 838, 378, 217, 595, 812, 408, 221, 629, 850, 480, 331, 811, 143, 954, 98, 53, 151, 204, 355, 559, 914, 474, 389, 863, 253, 117, 370, 487, 857, 345, 203, 548, 751, 300, 52, 352, 404, 756, 161, 917, 79, 996, 76, 73, 149, 222, 371, 593, 964, 558, 523, 82, 605, 687, 293, 980, 274, 255, 529, 784, 314, 99, 413, 512, 925, 438, 364, 802, 167, 969, 137, 107, 244, 351, 595, 946, 542, 489, 32, 521, 553, 75, 628, 703, 332, 36, 368, 404, 772, 177, 949, 127, 77, 204, 281, 485, 766, 252, 19, 271, 290, 561, 851, 413, 265, 678, 943, 622, 566, 189, 755, 944, 700, 645, 346, 991, 338, 330, 668, 998, 667, 666, 334, 1, 335, 336, 671, 8, 679, 687, 367, 55, 422, 477, 899, 377, 277, 654, 931, 586, 518, 105, 623, 728, 352, 81, 433, 514, 947, 462, 410, 872, 283, 156, 439, 595, 35, 630, 665, 296, 961, 258, 220, 478, 698, 177, 875, 53, 928, 981, 910, 892, 803, 696, 500, 197, 697, 894, 592, 487, 80, 567, 647, 215, 862, 78, 940, 19, 959, 978, 938, 917, 856, 774, 631, 406, 38, 444, 482, 926, 409, 336, 745, 82, 827, 909, 737, 647, 385, 33, 418, 451, 869, 321, 191, 512, 703, 216, 919, 136, 56, 192, 248, 440, 688, 129, 817, 946, 764, 711, 476, 188, 664, 852, 517, 370, 887, 258, 146, 404, 550, 954, 505, 460, 965, 426, 392, 818, 211, 30, 241, 271, 512, 783, 296, 80, 376, 456, 832, 289, 122, 411, 533, 944, 478, 423, 901, 325, 227, 552, 779, 332, 112, 444, 556, 1, 557, 558, 116, 674, 790, 465, 256, 721, 977, 699, 677, 377, 55, 432, 487, 919, 407, 327, 734, 62, 796, 858, 655, 514, 170, 684, 854, 539, 394, 933, 328, 262, 590, 852, 443, 296, 739, 36, 775, 811, 587, 399, 986, 386, 373, 759, 133, 892, 26, 918, 944, 863, 808, 672, 481, 154, 635, 789, 425, 215, 640, 855, 496, 352, 848, 201, 50, 251, 301, 552, 853, 406, 260, 666, 926, 593, 520, 114, 634, 748, 383, 132, 515, 647, 163, 810, 973, 784, 758, 543, 302, 845, 148, 993, 142, 136, 278, 414, 692, 107, 799, 906, 706, 613, 320, 933, 254, 188, 442, 630, 73, 703, 776, 480, 257, 737, 994, 732, 727, 460, 188, 648, 836, 485, 322, 807, 130, 937, 68, 6, 74, 80, 154, 234, 388, 622, 11, 633, 644, 278, 922, 201, 124, 325, 449, 774, 224, 998, 223, 222, 445, 667, 113, 780, 893, 674, 568, 243, 811, 55, 866, 921, 788, 710, 499, 210, 709, 919, 629, 549, 179, 728, 907, 636, 544, 181, 725, 906, 632, 539, 172, 711, 883, 595, 479, 75, 554, 629, 184, 813, 997, 811, 809, 621, 431, 53, 484, 537, 22, 559, 581, 141, 722, 863, 586, 450, 37, 487, 524, 12, 536, 548, 85, 633, 718, 352, 71, 423, 494, 917, 412, 330, 742, 73, 815, 888, 704, 593, 298, 891, 190, 82, 272, 354, 626, 980, 607, 588, 196, 784, 980, 765, 746, 512, 259, 771, 31, 802, 833, 636, 470, 107, 577, 684, 262, 946, 209, 156, 365, 521, 886, 408, 295, 703, 998, 702, 701, 404, 106, 510, 616, 127, 743, 870, 614, 485, 100, 585, 685, 271, 956, 228, 185, 413, 598, 12, 610, 622, 233, 855, 89, 944, 34, 978, 13, 991, 5, 996, 2, 998, 1, 0, 1, ... (permalink)

Of course, you don't need to start with 0 and 1 but the period ends up being the same regardless provided the starting numbers are less than the modulus, or so it appears after an admittedly brief investigation.

Let's look at some properties of this pisano period function. If \(m\) and \(n\) are coprime, then \( \pi(mn) \) is the least common multiple of \( \pi(m) \) and \( \pi(n) \). For example, \( \pi(55)=20\) while \( \pi(5) \times \pi(11)=\text{lcm}(20, 10)=20\) where 5 and 11 are coprime. To quote from the Wikipedia article: " ... the study of Pisano periods may be reduced to that of Pisano periods of prime powers \(q = p^k\), for \(k \geq 1\)". 

Furthermore, to continue quoting:

If \(p\) is prime, \( \pi(p^k)\) divides \(p^{k–1} \times  \pi(p)\). It is unknown if  \(\pi (p^{k})=p^{k-1}\pi (p)\) for every prime (p\) and integer \(k \gt 1\). Any prime \(p\) providing a counterexample would necessarily be a Wall–Sun–Sun prime ... So the study of Pisano periods may be further reduced to that of Pisano periods of primes.

Take 125 as an example. \( \pi(125)=500\). Now \(125=5^3\) and so \(500\) should divide \(5^2 \times \pi(5) = 25 \times 20 = 500\) which it does. The video link listed at the start of this post discusses the Wall-Sun-Sun primes.