GCD and Fibonacci Numbers - GeeksforGeeks

GCD and Fibonacci Numbers - GeeksforGeeks

You are given two positive numbers M and N. The task is to print greatest common divisor of M’th and N’th Fibonacci Numbers.

The first few Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….
Note that 0 is considered as 0'th Fibonacci Number.

GCD(Fib(M), Fib(N)) = Fib(GCD(M, N))

The above property holds because Fibonacci Numbers follow
Divisibility Sequence, i.e., if M divides N, then Fib(M)
also divides N. For example, Fib(3) = 2 and every third
third Fibonacci Number is even.

Source : Wiki

static final int MAX = 1000;     static int[] f;       gcdOfFibonacci()  // Constructor     {         // Create an array for memoization         f = new int[MAX];     }       // Returns n'th Fibonacci number using table f[].     // Refer method 6 of below post for details.     // http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/     private static int fib(int n)     {         // Base cases         if (n == 0)             return 0;         if (n == 1 || n == 2)             return (f[n] = 1);           // If fib(n) is already computed         if (f[n]!=0)             return f[n];           int k = ((n & 1)==1)? (n+1)/2 : n/2;           // Applying recursive formula [Note value n&1 is 1         // if n is odd, else 0.         f[n] = ((n & 1)==1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))                : (2*fib(k-1) + fib(k))*fib(k);           return f[n];     }       // Function to return gcd of a and b     private static int gcd(int M, int N)     {         if (M == 0)             return N;         return gcd(N%M, M);     }       // This method returns GCD of Fib(M) and Fib(N)     static int findGCDofFibMFibN(int M,  int N)     {         return fib(gcd(M, N));     }

Read full article from GCD and Fibonacci Numbers - GeeksforGeeks