Co-Prime Numbers in Java — Definition, Examples and Program

Co-Prime Numbers in Java — Definition, Examples and Program

Two numbers are called co-prime (or relatively prime) if their greatest common divisor (GCD) is 1. Co-prime numbers do not necessarily have to be prime themselves; they just should not share any common factors other than 1.

Examples of Co-Prime Numbers

• 8 and 15 → GCD(8,15) = 1 → Co-prime
• 14 and 15 → GCD(14,15) = 1 → Co-prime
• 12 and 18 → GCD(12,18) = 6 → Not Co-prime

How to Check Co-Prime Numbers?

1. Take two numbers as input.
2. Find their GCD using Euclid's algorithm.
3. If GCD = 1 → Numbers are Co-prime.
4. If GCD > 1 → Numbers are not Co-prime.

Java Program to Check Co-Prime Numbers

import java.util.Scanner;

public class CoPrimeNumbers {

    // Function to calculate GCD using Euclid's algorithm
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static boolean isCoPrime(int a, int b) {
        return gcd(a, b) == 1;
    }

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

        System.out.print("Enter first number: ");
        int num1 = sc.nextInt();

        System.out.print("Enter second number: ");
        int num2 = sc.nextInt();

        if (isCoPrime(num1, num2)) {
            System.out.println(num1 + " and " + num2 + " are Co-prime numbers");
        } else {
            System.out.println(num1 + " and " + num2 + " are NOT Co-prime numbers");
        }
    }
}

Sample Output

Enter first number: 8
Enter second number: 15
8 and 15 are Co-prime numbers

Enter first number: 12
Enter second number: 18
12 and 18 are NOT Co-prime numbers

Practice Challenges

1. Write a program to list all co-prime pairs between 1 and 50.
2. Modify the program to check if three numbers are mutually co-prime.
3. Write a program to count how many numbers are co-prime with a given number N.

Co-prime numbers are widely used in number theory, cryptography (RSA algorithm), and modular arithmetic. This Java program provides a quick way to check co-primality using the efficient Euclid’s algorithm.