A Coprime number comes in pair of integers. Thus they are defined as those paired numbers which can be divided by the common number 1 are called coprime numbers. Suppose a and b are two positive integers and they are divisible by only 1. Then a and b are co-prime number. For example 3 and 5 are only divisible by 1. Thus 3 and 5 are co-prime number. If a and b are divisible by some more numbers other than 1 then they are not co-prime number. For example 6 and 10 are not co-prime number. Because 6 and 10 are divisible 2 also other than 1. A coprime number is also known as relatively prime and mutually prime number.

## ALGORITHM TO CHECK COPRIME NUMBER

Suppose X and Y are two Integers. We have to check that whether these two numbers are coprime numbers. A number of methods are listed below.

**FIRST METHOD:**

**(Check Coprime Number)** Let I is a counter and it is initialized from 2. F is a Boolean variable and its value is 0. In this algorithm both numbers X and Y will be divided by I simultaneously. This division process will go on till I becomes equal to variable X. If X and Y are divisible for any value of I. Then value of F is changed to 1 and the loop will discontinue. If F is equal to 0 then X and Y are co-prime number. And if F is equal to 1 then both numbers are not co-prime.

Step 1: Start

Step 2: [ Take Inputs ] Read: X and Y

Step 3: [ Initializing Variables ] Set: I = 2 and F = 0

Step 4: Repeat While I <= X

Check If X%I == 0 AND Y%I == 0 Then

Set: F = 1 and break the loop

[ End of If Structure ]

Compute: I = I + 1

[ End of While Loop ]

Step 5: Check If F == 1 Then

Print: X and Y are Co-prime number.

Else

Print: X and Y are not Co-prime number.

Step 6: Exit

**SECOND METHOD:**

**(Check Coprime Number)** In this algorithm we will use an alternative definition of coprime number. If the GCD of two numbers is 1 then both number are co-prime. This algorithm first finds the GCD of X and Y. If GCD of X and Y is 1 then X and Y are coprime number. And if GCD of X and Y is some other value than 1 then X and Y are not coprime.

Step 1: Start

Step 2: [ Take Inputs ] Read: X and Y

Step 3: Repeat While A ≠ B

Step 3a: Check If A > B Then

Compute: A = A – B

Else

Set: Temp = A, A = B and B = Temp

Go To Step 3a

[ End of If Else Structure ]

[ End of While Loop ]

Step 4: set: GCD = A

Step 5: Check If GCD == 1 Then

Print: A and B are Co-prime number.

Else

Print: A and B are not Co-prime number.

Step 6: Exit

### FLOWCHART TO CHECK COPRIME NUMBER

**FIRST METHOD:**

**SECOND METHOD:**