login
Term preceding the first zero in the Fibonacci numbers modulo n.
4

%I #28 Jul 08 2019 04:06:06

%S 1,2,1,3,5,6,5,8,7,1,5,8,13,11,9,4,17,1,9,13,1,22,17,18,5,26,13,1,11,

%T 1,17,23,21,6,17,31,1,14,29,40,13,42,1,26,45,46,41,48,7,35,25,23,53,

%U 34,41,20,1,1,41,11,1,55,33,47,23,66,33,22,41,1,17,27

%N Term preceding the first zero in the Fibonacci numbers modulo n.

%C The multiplicative order of term n modulo n is given by sequence A001176.

%C Let M = [{1, 1}, {1, 0}], I = [{1, 0}, {0, 1}] is the 2 X 2 identity matrix, then A001177(n) is the smallest k > 0 such that M^k == r*I (mod n) for some r such that 0 <= r < n, and a(n) gives the value r. - _Jianing Song_, Jul 04 2019

%H Charles R Greathouse IV, <a href="/A217036/b217036.txt">Table of n, a(n) for n = 2..10000</a>

%F a(n) = F(G(n)-1) mod n where G(n) is sequence A001177 and F(m) is the m-th Fibonacci number. In particular, if n is a Fibonacci number, the n-th term is the previous Fibonacci number.

%F From _Jianing Song_, Jul 04 2019:

%F Also a(n) = F(G(n)+1) mod n.

%F a(2^e) = 1 if e = 1, 2, 2^(e-1) + 1 if e >= 3; a(p^e) = a(p)^(p^(e-1)) mod p^e for odd primes p.

%F For odd primes p, a(p^e) = 1 if and only if A001177(p) == 2 (mod 4); a(p^e) = p^e - 1 if and only if 4 divides A001177(p). (End)

%p a:= proc(n) local f, g; f, g:= 1, 0;

%p while f<>0 do f, g:= irem(f+g, n), f od; g

%p end:

%p seq(a(n), n=2..100); # _Alois P. Heinz_, Sep 24 2012

%t Table[k = 1; While[Mod[Fibonacci[k], n] > 0, k++]; Mod[Fibonacci[k - 1], n], {n, 2, 100}] (* _T. D. Noe_, Sep 24 2012 *)

%o (PARI) a(n)=my(a=0,b=1);for(k=1,n^2,[a,b]=[b,(a+b)%n];if(!b,return(a))) \\ _Charles R Greathouse IV_, Sep 24 2012

%K nonn

%O 2,2

%A _David Spies_, Sep 24 2012

%E a(14)-a(70) from _Charles R Greathouse IV_, Sep 24 2012