A104714 Greatest common divisor of a Fibonacci number and its index.

0, 1, 1, 1, 1, 5, 2, 1, 1, 1, 5, 1, 12, 1, 1, 5, 1, 1, 2, 1, 5, 1, 1, 1, 24, 25, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 36, 1, 1, 1, 5, 1, 2, 1, 1, 5, 1, 1, 48, 1, 25, 1, 1, 1, 2, 5, 7, 1, 1, 1, 60, 1, 1, 1, 1, 5, 2, 1, 1, 1, 5, 1, 72, 1, 1, 25, 1, 1, 2, 1, 5, 1, 1, 1, 12, 5, 1, 1, 1, 1, 10, 13, 1, 1, 1, 5, 96, 1

Offset: 0

Author

Harmel Nestra (harmel.nestra(AT)ut.ee), Apr 23 2005

Keywords

• easy
• nonn

Comments

Considering this sequence is a natural sequel to the investigation of the problem when F_n is divisible by n (the numbers occurring in A023172). This sequence has several nice properties. (1) n | m implies a(n) | a(m) for arbitrary naturals n and m. This property is a direct consequence of the analogous well-known property of Fibonacci numbers. (2) gcd (a(n), a(m)) = a(gcd(n, m)) for arbitrary naturals n and m. Also this property follows directly from the analogous (perhaps not so well-known) property of Fibonacci numbers. (3) a(n) * a(m) | a(n * m) for arbitrary naturals n and m. This property is remarkable especially in the light that the analogous proposition for Fibonacci numbers fails if n and m are not relatively prime (e.g. F_3 * F_3 does not divide F_9). (4) The set of numbers satisfying a(n) = n is closed w.r.t. multiplication. This follows easily from (3).

Examples

			The natural numbers:    0 1 2 3 4 5 6  7  8  9 10 11  12 ...
The Fibonacci numbers:  0 1 1 2 3 5 8 13 21 34 55 89 144 ...
The corresponding GCDs: 0 1 1 1 1 5 2  1  1  1  5  1  12 ...
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..20000 (first 1001 terms from T. D. Noe)
• Paolo Leonetti, Carlo Sanna, On the greatest common divisor of n and the nth Fibonacci number, arXiv:1704.00151 [math.NT], 2017.
• Carlo Sanna, Emanuele Tron, The density of numbers n having a prescribed G.C.D. with the nth Fibonacci number, arXiv:1705.01805 [math.NT], 2017.

Crossrefs

Cf. A023172, A000045, A001177, A001175, A001176. a(n) = gcd(A000045(n), A001477(n)). a(n) = n iff n occurs in A023172 iff n | A000045(n).

Cf. A074215 (a(n)==1).

Programs

Haskell

let fibs@(_ : fs) = 0 : 1 : zipWith (+) fibs fs in 0 : zipWith gcd [1 ..] fs

Maple

b:= proc(n) option remember; local r, M, p; r, M, p:=
      <<1|0>, <0|1>>, <<0|1>, <1|1>>, n;
      do if irem(p, 2, 'p')=1 then r:= r.M mod n fi;
         if p=0 then break fi; M:= M.M mod n
      od; r[1, 2]
    end:
a:= n-> igcd(n, b(n)):
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 05 2017

Mathematica

Table[GCD[Fibonacci[n],n],{n,0,97}] (* Alonso del Arte, Nov 22 2010 *)

PARI

a(n)=if(n,gcd(n,lift(Mod([1,1;1,0],n)^n)[1,2]),0) \\ Charles R Greathouse IV, Sep 24 2013

Formula

a(n) = gcd(F(n), n).