Check if sum of squares of first N fibonacci numbers is co-prime with Xth fibonacci number

fibonacci-numbersgcd-and-lcmnumber theory

This question is from an online coding platform.

Given two integers N and X, find whether sum of squares of fibonacci numbers from 1 to N (both inclusive) is co-prime with Xth fibonacci number or not.
Print "Yes" if it is divisible or "No" otherwise (without quotes).

Input:

  1. The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
  2. The first line of each test case contains two space-separated integers N and X.

Output: For each test case, print the answer.

Constraints:

  1. $1 ≤ T ≤ 10^5$
  2. $1 ≤ N, X ≤ 10^9$

Example:

Input:
2
4 2
23673332 12
Output:
Yes
No
Explanation:
Test Case 1 : F12 + F22 + F32 + F42 = 12 + 12 + 
22 + 32 = 1 + 1 + 4 + 9 = 15 and 15 is co-prime 
with F2 which is 1.

I came up with a solution which uses these facts:

  • $\sum_{i=0}^n F_i^2 = F_n.F_{n+1}$
  • $GCD(F_n, F_{n+1}) = 1$
  • $GCD(F_m, F_n) = F_{GCD(m, n)}$

Here my Java Solution but it is not getting accepted.

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int x = sc.nextInt();
            if (gcd(n, x) == 1 && gcd(n + 1, x) == 1) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }

        sc.close();
    }

    static long gcd(long a, long b) {
        if (b > a) {
            return gcd(b, a);
        }

        if (b == 0) {
            return a;
        }

        return gcd(b, a % b);
    }
}

If I change condition gcd(n, x) == 1 && gcd(n + 1, x) == 1 to gcd(n, x) <= 2 && gcd(n + 1, x) <= 2 then it gets accepted.

Can anyone shed some lights on why is this happening?

Best Answer

Now that I analyzed my solution again I foud out that I was making a silly mistak.

Let me show what

If I change condition gcd(n, x) == 1 && gcd(n + 1, x) == 1 to gcd(n, x) <= 2 && gcd(n + 1, x) <= 2 then it gets accepted.

The problem lies in the fact that $GCD(F_m, F_n) = F_{GCD(n, m)}$ hence whenever gcd(n, x) <= 2 && gcd(n + 1, x) <= 2 is true we know for sure that $F_1 = 1$ or $F_2 = 1$ is the answer respectively.

Hence

$$GCD(F_n, F_m) = 1$$ will always be true(since $F_1 = 1$ and $F_2 = 1$).

Related Question