A217036 Term preceding the first zero in the Fibonacci numbers modulo n.

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, 1, 17, 23, 21, 6, 17, 31, 1, 14, 29, 40, 13, 42, 1, 26, 45, 46, 41, 48, 7, 35, 25, 23, 53, 34, 41, 20, 1, 1, 41, 11, 1, 55, 33, 47, 23, 66, 33, 22, 41, 1, 17, 27

Offset: 2

Author

David Spies, Sep 24 2012

Keywords

• nonn

Comments

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

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

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 2..10000

Programs

Maple

a:= proc(n) local f, g; f, g:= 1, 0;
      while f<>0 do f, g:= irem(f+g, n), f od; g
    end:
seq(a(n), n=2..100);  # Alois P. Heinz, Sep 24 2012

Mathematica

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

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

Formula

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.

From Jianing Song, Jul 04 2019: (Start)

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

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.

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)

Extensions

a(14)-a(70) from Charles R Greathouse IV, Sep 24 2012