2022.03.07 MATH 3600 Fib mod m

115 days ago by calkin

Compute the fibonacci sequence mod p for various primes p

p=5 fmodp=[] for i in srange(p^2): fmodp.append([i,mod(fibonacci(i) ,p)]) print(fmodp) 
       
[[0, 0], [1, 1], [2, 1], [3, 2], [4, 3], [5, 0], [6, 3], [7, 3], [8, 1],
[9, 4], [10, 0], [11, 4], [12, 4], [13, 3], [14, 2], [15, 0], [16, 2],
[17, 2], [18, 4], [19, 1], [20, 0], [21, 1], [22, 1], [23, 2], [24, 3]]
[[0, 0], [1, 1], [2, 1], [3, 2], [4, 3], [5, 0], [6, 3], [7, 3], [8, 1], [9, 4], [10, 0], [11, 4], [12, 4], [13, 3], [14, 2], [15, 0], [16, 2], [17, 2], [18, 4], [19, 1], [20, 0], [21, 1], [22, 1], [23, 2], [24, 3]]

Mod 5, the sequence has period 20.

p=7 fmodp=[] for i in srange(p^2): fmodp.append([i,mod(fibonacci(i) ,p)]) print(fmodp) 
       
[[0, 0], [1, 1], [2, 1], [3, 2], [4, 3], [5, 5], [6, 1], [7, 6], [8, 0],
[9, 6], [10, 6], [11, 5], [12, 4], [13, 2], [14, 6], [15, 1], [16, 0],
[17, 1], [18, 1], [19, 2], [20, 3], [21, 5], [22, 1], [23, 6], [24, 0],
[25, 6], [26, 6], [27, 5], [28, 4], [29, 2], [30, 6], [31, 1], [32, 0],
[33, 1], [34, 1], [35, 2], [36, 3], [37, 5], [38, 1], [39, 6], [40, 0],
[41, 6], [42, 6], [43, 5], [44, 4], [45, 2], [46, 6], [47, 1], [48, 0]]
[[0, 0], [1, 1], [2, 1], [3, 2], [4, 3], [5, 5], [6, 1], [7, 6], [8, 0], [9, 6], [10, 6], [11, 5], [12, 4], [13, 2], [14, 6], [15, 1], [16, 0], [17, 1], [18, 1], [19, 2], [20, 3], [21, 5], [22, 1], [23, 6], [24, 0], [25, 6], [26, 6], [27, 5], [28, 4], [29, 2], [30, 6], [31, 1], [32, 0], [33, 1], [34, 1], [35, 2], [36, 3], [37, 5], [38, 1], [39, 6], [40, 0], [41, 6], [42, 6], [43, 5], [44, 4], [45, 2], [46, 6], [47, 1], [48, 0]]

Mod 7 the period is 16.  

Observation: 48/16=3.

p=11 fmodp=[] for i in srange(p^2): fmodp.append([i,mod(fibonacci(i) ,p)]) print(fmodp) 
       
[[0, 0], [1, 1], [2, 1], [3, 2], [4, 3], [5, 5], [6, 8], [7, 2], [8,
10], [9, 1], [10, 0], [11, 1], [12, 1], [13, 2], [14, 3], [15, 5], [16,
8], [17, 2], [18, 10], [19, 1], [20, 0], [21, 1], [22, 1], [23, 2], [24,
3], [25, 5], [26, 8], [27, 2], [28, 10], [29, 1], [30, 0], [31, 1], [32,
1], [33, 2], [34, 3], [35, 5], [36, 8], [37, 2], [38, 10], [39, 1], [40,
0], [41, 1], [42, 1], [43, 2], [44, 3], [45, 5], [46, 8], [47, 2], [48,
10], [49, 1], [50, 0], [51, 1], [52, 1], [53, 2], [54, 3], [55, 5], [56,
8], [57, 2], [58, 10], [59, 1], [60, 0], [61, 1], [62, 1], [63, 2], [64,
3], [65, 5], [66, 8], [67, 2], [68, 10], [69, 1], [70, 0], [71, 1], [72,
1], [73, 2], [74, 3], [75, 5], [76, 8], [77, 2], [78, 10], [79, 1], [80,
0], [81, 1], [82, 1], [83, 2], [84, 3], [85, 5], [86, 8], [87, 2], [88,
10], [89, 1], [90, 0], [91, 1], [92, 1], [93, 2], [94, 3], [95, 5], [96,
8], [97, 2], [98, 10], [99, 1], [100, 0], [101, 1], [102, 1], [103, 2],
[104, 3], [105, 5], [106, 8], [107, 2], [108, 10], [109, 1], [110, 0],
[111, 1], [112, 1], [113, 2], [114, 3], [115, 5], [116, 8], [117, 2],
[118, 10], [119, 1], [120, 0]]
[[0, 0], [1, 1], [2, 1], [3, 2], [4, 3], [5, 5], [6, 8], [7, 2], [8, 10], [9, 1], [10, 0], [11, 1], [12, 1], [13, 2], [14, 3], [15, 5], [16, 8], [17, 2], [18, 10], [19, 1], [20, 0], [21, 1], [22, 1], [23, 2], [24, 3], [25, 5], [26, 8], [27, 2], [28, 10], [29, 1], [30, 0], [31, 1], [32, 1], [33, 2], [34, 3], [35, 5], [36, 8], [37, 2], [38, 10], [39, 1], [40, 0], [41, 1], [42, 1], [43, 2], [44, 3], [45, 5], [46, 8], [47, 2], [48, 10], [49, 1], [50, 0], [51, 1], [52, 1], [53, 2], [54, 3], [55, 5], [56, 8], [57, 2], [58, 10], [59, 1], [60, 0], [61, 1], [62, 1], [63, 2], [64, 3], [65, 5], [66, 8], [67, 2], [68, 10], [69, 1], [70, 0], [71, 1], [72, 1], [73, 2], [74, 3], [75, 5], [76, 8], [77, 2], [78, 10], [79, 1], [80, 0], [81, 1], [82, 1], [83, 2], [84, 3], [85, 5], [86, 8], [87, 2], [88, 10], [89, 1], [90, 0], [91, 1], [92, 1], [93, 2], [94, 3], [95, 5], [96, 8], [97, 2], [98, 10], [99, 1], [100, 0], [101, 1], [102, 1], [103, 2], [104, 3], [105, 5], [106, 8], [107, 2], [108, 10], [109, 1], [110, 0], [111, 1], [112, 1], [113, 2], [114, 3], [115, 5], [116, 8], [117, 2], [118, 10], [119, 1], [120, 0]]

Mod 11 the period is 10 = p-1 which divides $p^2-1$.

Can we find any patterns to the length of the period?

Except for $p=5$, does the period mod $p$ always divide $p^2-1$?

p=13 fmodp=[] for i in srange(p^2): fmodp.append([i,mod(fibonacci(i) ,p)]) print(fmodp) 
       
[[0, 0], [1, 1], [2, 1], [3, 2], [4, 3], [5, 5], [6, 8], [7, 0], [8, 8],
[9, 8], [10, 3], [11, 11], [12, 1], [13, 12], [14, 0], [15, 12], [16,
12], [17, 11], [18, 10], [19, 8], [20, 5], [21, 0], [22, 5], [23, 5],
[24, 10], [25, 2], [26, 12], [27, 1], [28, 0], [29, 1], [30, 1], [31,
2], [32, 3], [33, 5], [34, 8], [35, 0], [36, 8], [37, 8], [38, 3], [39,
11], [40, 1], [41, 12], [42, 0], [43, 12], [44, 12], [45, 11], [46, 10],
[47, 8], [48, 5], [49, 0], [50, 5], [51, 5], [52, 10], [53, 2], [54,
12], [55, 1], [56, 0], [57, 1], [58, 1], [59, 2], [60, 3], [61, 5], [62,
8], [63, 0], [64, 8], [65, 8], [66, 3], [67, 11], [68, 1], [69, 12],
[70, 0], [71, 12], [72, 12], [73, 11], [74, 10], [75, 8], [76, 5], [77,
0], [78, 5], [79, 5], [80, 10], [81, 2], [82, 12], [83, 1], [84, 0],
[85, 1], [86, 1], [87, 2], [88, 3], [89, 5], [90, 8], [91, 0], [92, 8],
[93, 8], [94, 3], [95, 11], [96, 1], [97, 12], [98, 0], [99, 12], [100,
12], [101, 11], [102, 10], [103, 8], [104, 5], [105, 0], [106, 5], [107,
5], [108, 10], [109, 2], [110, 12], [111, 1], [112, 0], [113, 1], [114,
1], [115, 2], [116, 3], [117, 5], [118, 8], [119, 0], [120, 8], [121,
8], [122, 3], [123, 11], [124, 1], [125, 12], [126, 0], [127, 12], [128,
12], [129, 11], [130, 10], [131, 8], [132, 5], [133, 0], [134, 5], [135,
5], [136, 10], [137, 2], [138, 12], [139, 1], [140, 0], [141, 1], [142,
1], [143, 2], [144, 3], [145, 5], [146, 8], [147, 0], [148, 8], [149,
8], [150, 3], [151, 11], [152, 1], [153, 12], [154, 0], [155, 12], [156,
12], [157, 11], [158, 10], [159, 8], [160, 5], [161, 0], [162, 5], [163,
5], [164, 10], [165, 2], [166, 12], [167, 1], [168, 0]]
[[0, 0], [1, 1], [2, 1], [3, 2], [4, 3], [5, 5], [6, 8], [7, 0], [8, 8], [9, 8], [10, 3], [11, 11], [12, 1], [13, 12], [14, 0], [15, 12], [16, 12], [17, 11], [18, 10], [19, 8], [20, 5], [21, 0], [22, 5], [23, 5], [24, 10], [25, 2], [26, 12], [27, 1], [28, 0], [29, 1], [30, 1], [31, 2], [32, 3], [33, 5], [34, 8], [35, 0], [36, 8], [37, 8], [38, 3], [39, 11], [40, 1], [41, 12], [42, 0], [43, 12], [44, 12], [45, 11], [46, 10], [47, 8], [48, 5], [49, 0], [50, 5], [51, 5], [52, 10], [53, 2], [54, 12], [55, 1], [56, 0], [57, 1], [58, 1], [59, 2], [60, 3], [61, 5], [62, 8], [63, 0], [64, 8], [65, 8], [66, 3], [67, 11], [68, 1], [69, 12], [70, 0], [71, 12], [72, 12], [73, 11], [74, 10], [75, 8], [76, 5], [77, 0], [78, 5], [79, 5], [80, 10], [81, 2], [82, 12], [83, 1], [84, 0], [85, 1], [86, 1], [87, 2], [88, 3], [89, 5], [90, 8], [91, 0], [92, 8], [93, 8], [94, 3], [95, 11], [96, 1], [97, 12], [98, 0], [99, 12], [100, 12], [101, 11], [102, 10], [103, 8], [104, 5], [105, 0], [106, 5], [107, 5], [108, 10], [109, 2], [110, 12], [111, 1], [112, 0], [113, 1], [114, 1], [115, 2], [116, 3], [117, 5], [118, 8], [119, 0], [120, 8], [121, 8], [122, 3], [123, 11], [124, 1], [125, 12], [126, 0], [127, 12], [128, 12], [129, 11], [130, 10], [131, 8], [132, 5], [133, 0], [134, 5], [135, 5], [136, 10], [137, 2], [138, 12], [139, 1], [140, 0], [141, 1], [142, 1], [143, 2], [144, 3], [145, 5], [146, 8], [147, 0], [148, 8], [149, 8], [150, 3], [151, 11], [152, 1], [153, 12], [154, 0], [155, 12], [156, 12], [157, 11], [158, 10], [159, 8], [160, 5], [161, 0], [162, 5], [163, 5], [164, 10], [165, 2], [166, 12], [167, 1], [168, 0]]
p=17 fmodp=[] for i in srange(p^2): fmodp.append([i,mod(fibonacci(i) ,p)]) print(fmodp) 
       
[[0, 0], [1, 1], [2, 1], [3, 2], [4, 3], [5, 5], [6, 8], [7, 13], [8,
4], [9, 0], [10, 4], [11, 4], [12, 8], [13, 12], [14, 3], [15, 15], [16,
1], [17, 16], [18, 0], [19, 16], [20, 16], [21, 15], [22, 14], [23, 12],
[24, 9], [25, 4], [26, 13], [27, 0], [28, 13], [29, 13], [30, 9], [31,
5], [32, 14], [33, 2], [34, 16], [35, 1], [36, 0], [37, 1], [38, 1],
[39, 2], [40, 3], [41, 5], [42, 8], [43, 13], [44, 4], [45, 0], [46, 4],
[47, 4], [48, 8], [49, 12], [50, 3], [51, 15], [52, 1], [53, 16], [54,
0], [55, 16], [56, 16], [57, 15], [58, 14], [59, 12], [60, 9], [61, 4],
[62, 13], [63, 0], [64, 13], [65, 13], [66, 9], [67, 5], [68, 14], [69,
2], [70, 16], [71, 1], [72, 0], [73, 1], [74, 1], [75, 2], [76, 3], [77,
5], [78, 8], [79, 13], [80, 4], [81, 0], [82, 4], [83, 4], [84, 8], [85,
12], [86, 3], [87, 15], [88, 1], [89, 16], [90, 0], [91, 16], [92, 16],
[93, 15], [94, 14], [95, 12], [96, 9], [97, 4], [98, 13], [99, 0], [100,
13], [101, 13], [102, 9], [103, 5], [104, 14], [105, 2], [106, 16],
[107, 1], [108, 0], [109, 1], [110, 1], [111, 2], [112, 3], [113, 5],
[114, 8], [115, 13], [116, 4], [117, 0], [118, 4], [119, 4], [120, 8],
[121, 12], [122, 3], [123, 15], [124, 1], [125, 16], [126, 0], [127,
16], [128, 16], [129, 15], [130, 14], [131, 12], [132, 9], [133, 4],
[134, 13], [135, 0], [136, 13], [137, 13], [138, 9], [139, 5], [140,
14], [141, 2], [142, 16], [143, 1], [144, 0], [145, 1], [146, 1], [147,
2], [148, 3], [149, 5], [150, 8], [151, 13], [152, 4], [153, 0], [154,
4], [155, 4], [156, 8], [157, 12], [158, 3], [159, 15], [160, 1], [161,
16], [162, 0], [163, 16], [164, 16], [165, 15], [166, 14], [167, 12],
[168, 9], [169, 4], [170, 13], [171, 0], [172, 13], [173, 13], [174, 9],
[175, 5], [176, 14], [177, 2], [178, 16], [179, 1], [180, 0], [181, 1],
[182, 1], [183, 2], [184, 3], [185, 5], [186, 8], [187, 13], [188, 4],
[189, 0], [190, 4], [191, 4], [192, 8], [193, 12], [194, 3], [195, 15],
[196, 1], [197, 16], [198, 0], [199, 16], [200, 16], [201, 15], [202,
14], [203, 12], [204, 9], [205, 4], [206, 13], [207, 0], [208, 13],
[209, 13], [210, 9], [211, 5], [212, 14], [213, 2], [214, 16], [215, 1],
[216, 0], [217, 1], [218, 1], [219, 2], [220, 3], [221, 5], [222, 8],
[223, 13], [224, 4], [225, 0], [226, 4], [227, 4], [228, 8], [229, 12],
[230, 3], [231, 15], [232, 1], [233, 16], [234, 0], [235, 16], [236,
16], [237, 15], [238, 14], [239, 12], [240, 9], [241, 4], [242, 13],
[243, 0], [244, 13], [245, 13], [246, 9], [247, 5], [248, 14], [249, 2],
[250, 16], [251, 1], [252, 0], [253, 1], [254, 1], [255, 2], [256, 3],
[257, 5], [258, 8], [259, 13], [260, 4], [261, 0], [262, 4], [263, 4],
[264, 8], [265, 12], [266, 3], [267, 15], [268, 1], [269, 16], [270, 0],
[271, 16], [272, 16], [273, 15], [274, 14], [275, 12], [276, 9], [277,
4], [278, 13], [279, 0], [280, 13], [281, 13], [282, 9], [283, 5], [284,
14], [285, 2], [286, 16], [287, 1], [288, 0]]
[[0, 0], [1, 1], [2, 1], [3, 2], [4, 3], [5, 5], [6, 8], [7, 13], [8, 4], [9, 0], [10, 4], [11, 4], [12, 8], [13, 12], [14, 3], [15, 15], [16, 1], [17, 16], [18, 0], [19, 16], [20, 16], [21, 15], [22, 14], [23, 12], [24, 9], [25, 4], [26, 13], [27, 0], [28, 13], [29, 13], [30, 9], [31, 5], [32, 14], [33, 2], [34, 16], [35, 1], [36, 0], [37, 1], [38, 1], [39, 2], [40, 3], [41, 5], [42, 8], [43, 13], [44, 4], [45, 0], [46, 4], [47, 4], [48, 8], [49, 12], [50, 3], [51, 15], [52, 1], [53, 16], [54, 0], [55, 16], [56, 16], [57, 15], [58, 14], [59, 12], [60, 9], [61, 4], [62, 13], [63, 0], [64, 13], [65, 13], [66, 9], [67, 5], [68, 14], [69, 2], [70, 16], [71, 1], [72, 0], [73, 1], [74, 1], [75, 2], [76, 3], [77, 5], [78, 8], [79, 13], [80, 4], [81, 0], [82, 4], [83, 4], [84, 8], [85, 12], [86, 3], [87, 15], [88, 1], [89, 16], [90, 0], [91, 16], [92, 16], [93, 15], [94, 14], [95, 12], [96, 9], [97, 4], [98, 13], [99, 0], [100, 13], [101, 13], [102, 9], [103, 5], [104, 14], [105, 2], [106, 16], [107, 1], [108, 0], [109, 1], [110, 1], [111, 2], [112, 3], [113, 5], [114, 8], [115, 13], [116, 4], [117, 0], [118, 4], [119, 4], [120, 8], [121, 12], [122, 3], [123, 15], [124, 1], [125, 16], [126, 0], [127, 16], [128, 16], [129, 15], [130, 14], [131, 12], [132, 9], [133, 4], [134, 13], [135, 0], [136, 13], [137, 13], [138, 9], [139, 5], [140, 14], [141, 2], [142, 16], [143, 1], [144, 0], [145, 1], [146, 1], [147, 2], [148, 3], [149, 5], [150, 8], [151, 13], [152, 4], [153, 0], [154, 4], [155, 4], [156, 8], [157, 12], [158, 3], [159, 15], [160, 1], [161, 16], [162, 0], [163, 16], [164, 16], [165, 15], [166, 14], [167, 12], [168, 9], [169, 4], [170, 13], [171, 0], [172, 13], [173, 13], [174, 9], [175, 5], [176, 14], [177, 2], [178, 16], [179, 1], [180, 0], [181, 1], [182, 1], [183, 2], [184, 3], [185, 5], [186, 8], [187, 13], [188, 4], [189, 0], [190, 4], [191, 4], [192, 8], [193, 12], [194, 3], [195, 15], [196, 1], [197, 16], [198, 0], [199, 16], [200, 16], [201, 15], [202, 14], [203, 12], [204, 9], [205, 4], [206, 13], [207, 0], [208, 13], [209, 13], [210, 9], [211, 5], [212, 14], [213, 2], [214, 16], [215, 1], [216, 0], [217, 1], [218, 1], [219, 2], [220, 3], [221, 5], [222, 8], [223, 13], [224, 4], [225, 0], [226, 4], [227, 4], [228, 8], [229, 12], [230, 3], [231, 15], [232, 1], [233, 16], [234, 0], [235, 16], [236, 16], [237, 15], [238, 14], [239, 12], [240, 9], [241, 4], [242, 13], [243, 0], [244, 13], [245, 13], [246, 9], [247, 5], [248, 14], [249, 2], [250, 16], [251, 1], [252, 0], [253, 1], [254, 1], [255, 2], [256, 3], [257, 5], [258, 8], [259, 13], [260, 4], [261, 0], [262, 4], [263, 4], [264, 8], [265, 12], [266, 3], [267, 15], [268, 1], [269, 16], [270, 0], [271, 16], [272, 16], [273, 15], [274, 14], [275, 12], [276, 9], [277, 4], [278, 13], [279, 0], [280, 13], [281, 13], [282, 9], [283, 5], [284, 14], [285, 2], [286, 16], [287, 1], [288, 0]]

Let us see if we can be more systematic about how to explore the period modulo $p$.

Looking at the data from $p=17$, we see that the period is 36.  Moreover, we observe that 

$F_9,F_{18}, F_{27}$ are all zero mod $p$.  Can we describe this pattern?   

It appears that $F_n\equiv 0 (\mod 17)$ if and only if $n$ is a multiple of 9. 

Can you explain why it must be the case that the positions of the zeros must repeat in a periodic fashion with period dividing the full period $\mod p$. 

Let us define the Pisano period $\pi(m)$ to be the period with which $F_n$ repeats mod $m$.  

Here is an algorithm to compute $\pi(m)$.

Compute $F_n (\mod m)$ until we see a value $n$ for which $F_n \equiv 0 \mod m$.

Now compute $F_{kn+1}$ for $k=0,1,2,\dots$ until we see a value for which $F_{kn+1} \equiv 1 \mod m$.

Then $\pi(m) = kn$.  This will require computing about $n+k$ values rather than the $nk$ values that a naive approach might need.

def pisano(m): n=1 while mod(fibonacci(n),m) != 0: n+=1 #at this stage, F_n is 0 mod m k=1 while mod(fibonacci(k*n+1),m) !=1: k+=1 return(n*k) 
       
Traceback (click to the left of this block for traceback)
...
NameError: name '_interact_' is not defined
Traceback (most recent call last):        #at this stage, F_n is 0 mod m
NameError: name '_interact_' is not defined
pisano(17) 
       
36
36

This appears to agree with what we have computed thus far.  

Now let's be systematic about collecting data: create a list of primes and the corresponding pisano periods.

pisano_list=[] p=2 while p<20: pisano_list.append([p,pisano(p)]) p=p.next_prime() 
       
print(pisano_list) 
       
[[2, 3], [3, 8], [5, 20], [7, 16], [11, 10], [13, 28], [17, 36], [19,
18]]
[[2, 3], [3, 8], [5, 20], [7, 16], [11, 10], [13, 28], [17, 36], [19, 18]]

Now we see that this seems to work, let's generate more data.

pisano_list=[] p=2 while p<2000: pisano_list.append([p,pisano(p)]) p=p.next_prime() 
       
list_plot(pisano_list) 
       
pisano_list=[] p=2 while p<10000: pisano_list.append([p,pisano(p)]) p=p.next_prime() 
       
list_plot(pisano_list) 
       

Some observations.

First, the code is slowing down a lot at this point.  Perhaps we can find a better way to compute pisano(m)?

Second, we are clearly seeing what looks like a linear structure here.

My eyes see at least five lines that the points appear to lie on, or near

$y=2x, y=x,$ and perhaps several lines like $y=cx$ where $c$ needs to be determined: the first one looks to be perhaps a bit bigger than $y=x/2$: perhaps it is $y=2x/3?$

Can we identify which points lie on or near the line $y=2x$?

A=list_plot(pisano_list) B=plot(x/4,x,0,10000,color='red') show(A+B) 
       
small_values=pisano_list[:50] 
       
list_plot(small_values) 
       
for val in small_values: if val[1]==2*val[0]: print(val) 
       

None of them are exactly double!

for val in small_values: if val[1]==2*val[0]+2: print(val) 
       
[3, 8]
[7, 16]
[13, 28]
[17, 36]
[23, 48]
[37, 76]
[43, 88]
[53, 108]
[67, 136]
[73, 148]
[83, 168]
[97, 196]
[103, 208]
[127, 256]
[137, 276]
[157, 316]
[163, 328]
[167, 336]
[173, 348]
[193, 388]
[197, 396]
[223, 448]
[227, 456]
[3, 8]
[7, 16]
[13, 28]
[17, 36]
[23, 48]
[37, 76]
[43, 88]
[53, 108]
[67, 136]
[73, 148]
[83, 168]
[97, 196]
[103, 208]
[127, 256]
[137, 276]
[157, 316]
[163, 328]
[167, 336]
[173, 348]
[193, 388]
[197, 396]
[223, 448]
[227, 456]

The primes for which $\pi(p)=2(p+1)$ appear to all be congruent to 2 or 3 mod 5.

for val in small_values: if val[1]==val[0]-1: print(val) 
       
[11, 10]
[19, 18]
[31, 30]
[41, 40]
[59, 58]
[61, 60]
[71, 70]
[79, 78]
[109, 108]
[131, 130]
[149, 148]
[179, 178]
[191, 190]
[11, 10]
[19, 18]
[31, 30]
[41, 40]
[59, 58]
[61, 60]
[71, 70]
[79, 78]
[109, 108]
[131, 130]
[149, 148]
[179, 178]
[191, 190]

The primes for which $\pi(p)=p-1$ appear to all be congruent to 1 or 4 mod 5.

Observation: if $p$ is a prime other than 2 or 5,  $p-1$ is odd, so both $2(p+1)$ and $(p-1)$ divide $p^2-1=(p+1)(p-1)$

Let us see if there are primes for which $\pi(p)$ does not divide $p^2-1$.

for val in pisano_list: if mod(val[0]^2-1, val[1])!=0: print(val) 
       
[5, 20]
[5, 20]

Perhaps a faster algorithm to compute $\pi(p)$ might be to find all the divisors of $2(p+1)$ or $(p-1)$ and find the smallest divisor $d$ so that $F_d==0$ and $F_{d+1}==1$ mod $p$.

for val in pisano_list: if val[1] ==val[0]+1: print(val) 
       
[2, 3]
[2, 3]
 
       

We have seen that for some primes $p$, we can find square root of 5 mod $p$

(for example, $p=11$) and for others we cannot, (e.g. $p=7$).

Let us explore this.

a=mod(5,11) sqrt(a) 
       
4
4
a=mod(5,7) sqrt(a) 
       
sqrt5
sqrt5
sqrt(a)==sqrt(5) 
       
sqrt5 == sqrt(5)
sqrt5 == sqrt(5)
type(sqrt(a)) 
       
<type
'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement'>
<type 'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement'>
Integer(sqrt(a)) 
       
Traceback (click to the left of this block for traceback)
...
TypeError: not in prime subfield
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_8.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("SW50ZWdlcihzcXJ0KGEpKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmpuUUX9h/___code___.py", line 2, in <module>
    exec compile(u'Integer(sqrt(a))
  File "", line 1, in <module>
    
  File "sage/rings/integer.pyx", line 662, in sage.rings.integer.Integer.__init__ (/usr/local/sage-6.10/src/build/cythonized/sage/rings/integer.c:5806)
  File "sage/rings/finite_rings/element_givaro.pyx", line 1397, in sage.rings.finite_rings.element_givaro.FiniteField_givaroElement._integer_ (/usr/local/sage-6.10/src/build/cythonized/sage/rings/finite_rings/element_givaro.cpp:13470)
TypeError: not in prime subfield
1==2 
       
False
False
p=7 while p<100: a=mod(5,p) print(p,sqrt(a)) p=p.next_prime() 
       
(7, sqrt5)
(11, 4)
(13, sqrt5)
(17, sqrt5)
(19, 9)
(23, sqrt5)
(29, 11)
(31, 6)
(37, sqrt5)
(41, 13)
(43, sqrt5)
(47, sqrt5)
(53, sqrt5)
(59, 8)
(61, 26)
(67, sqrt5)
(71, 17)
(73, sqrt5)
(79, 20)
(83, sqrt5)
(89, 19)
(97, sqrt5)
(7, sqrt5)
(11, 4)
(13, sqrt5)
(17, sqrt5)
(19, 9)
(23, sqrt5)
(29, 11)
(31, 6)
(37, sqrt5)
(41, 13)
(43, sqrt5)
(47, sqrt5)
(53, sqrt5)
(59, 8)
(61, 26)
(67, sqrt5)
(71, 17)
(73, sqrt5)
(79, 20)
(83, sqrt5)
(89, 19)
(97, sqrt5)

It appears that if $p$ is congruent to 1,4 mod 5, then 5 has a square root mod $p$.  If $p$ is congruent to 2,3 mdo 5, then 5 does not have a square root mod p.

p=59 a=mod(27,p) (a^(p-1)) 
       
1
1

We see then that Fermat's little theorem, together with the explicit formula for $F_n$ in terms of $\sqrt{5}$, implies that if $p=1,4$ mod 5, then the Pisano period must divide $p-1$.


The case $p=2,3$ mod 5 is more complicated.   It is, however, the case that the period in this case must divide $2(p+1)$.

We are not interested in the Pisano period for big primes, but rather for the period mod $10^{20}$.

pisano(5) 
       
20
20
pisano(25) 
       
100
100
for k in srange(1,10): print(k,pisano(5^k)) 
       
(1, 20)
(2, 100)
(3, 500)
(4, 2500)
(5, 12500)
(6, 62500)
(7, 312500)
(1, 20)
(2, 100)
(3, 500)
(4, 2500)
(5, 12500)
(6, 62500)
(7, 312500)

Some observations our pisano code has slowed down enough that it's probably not going to be possible to compute $\pi(10^{20})$.

We might, however, be able to conjecture $\pi(5^k)$ and $\pi(2^k)$.

Their least common multiple will be $\pi(10^k)$.

def pisano(m): n=1 while mod(fibonacci(n),m) != 0: n+=1 print("first zoro at", n) k=1 while mod(fibonacci(k*n+1),m) !=1: k+=1 return(n*k) 
       
for k in srange(1,10): print(k,pisano(2^k)) 
       
(1, 3)
(2, 6)
(3, 12)
(4, 24)
(5, 48)
(6, 96)
(7, 192)
(8, 384)
(9, 768)
(1, 3)
(2, 6)
(3, 12)
(4, 24)
(5, 48)
(6, 96)
(7, 192)
(8, 384)
(9, 768)
for k in srange(1,7): print(k,pisano(5^k)) 
       
('first zoro at', 5)
(1, 20)
('first zoro at', 25)
(2, 100)
('first zoro at', 125)
(3, 500)
('first zoro at', 625)
(4, 2500)
('first zoro at', 3125)
(5, 12500)
('first zoro at', 15625)
(6, 62500)
('first zoro at', 5)
(1, 20)
('first zoro at', 25)
(2, 100)
('first zoro at', 125)
(3, 500)
('first zoro at', 625)
(4, 2500)
('first zoro at', 3125)
(5, 12500)
('first zoro at', 15625)
(6, 62500)
def check_pisano_5(k): v=4*5^k u=5^k w=2*u+1 x=v+1 if (mod(fibonacci(u),u)==0) and (mod(fibonacci(w),u)!=1) and (mod(fibonacci(x),u)==1): return(True) 
       
check_pisano_5(2) 
       
True
True
for k in srange(21): print(k,check_pisano_5(k)) 
       
(0, None)
(1, True)
(2, True)
(3, True)
(4, True)
(5, True)
(6, True)
(7, True)
(8, True)
(9, True)
(10, True)
(11, True)
(12, True)
(0, None)
(1, True)
(2, True)
(3, True)
(4, True)
(5, True)
(6, True)
(7, True)
(8, True)
(9, True)
(10, True)
(11, True)
(12, True)