Co-primes

I. Definitions

When two numbers do not have a common factor greater than $1$, they are called co-primes. To find whether two numbers are co-primes or not, we need to find out the $GCD$ of the two numbers. If the $GCD$ is greater than $1$, then the numbers are not co-prime, otherwise, if their $GCD$ is equal to $1$, then the numbers form a co-prime pair.

For example, the numbers $156$ and $108$ have a $GCD$ of $12$, hence they are not co-primes. But the numbers $188$ and $135$ have a $GCD$ of $1$. Hence they are co-primes.

-----------book page break-----------

II. Some Observations On Co-Primes

Few interesting things to remember:

- The number $1$ is considered as co-prime to any other number, since any number and $1$ will always have a $GCD$ of

$one$

- Any two consecutive numbers are always co-prime. For example $133$, $134$ form co-prime pairs. This is because if the smaller number is divisible by any factor greater than $1$, the next number will leave a remainder of $1$ when divided by the same factor. Therefore, any two consecutive numbers cannot be divisible by the same number greater than $1$.

- Any two consecutive odd numbers will always be co-prime. Because, as we learnt , the HCF of two number cannot be greater than their difference. The difference between any two consecutive odd number is always two. Hence their HCF can be at most $2$. But since they are odd numbers, they are not divisible by $2$. Therefore, their HCF can only be $1$, and so, they are co-primes.

- Any two alternate odd numbers are also co-primes. The difference between any two alternate odd numbers is

$four$

. Since they are odd numbers, they cannot have $2$ or $4$ as their factors. Therefore, the only HCF they can have is $3$. If any one of them is divisible by $3$, then the other cannot be divisible by $3$. Because, if any one of the numbers, let us say $N$ is divisible by $3$ then, $N-3$ and $N+3$ will be divisible by $3$ while $N-4$ and $N+4$ cannot be divisible by $3$. That is why any two alternate odd numbers are always co-prime. For example $139$ and $143$, or $1983$ and $1987$

- Every prime number is co-prime to all numbers less than itself. Since prime numbers do not have any factor other than $1$, it cannot share a common factor with any number smaller than itself.

-----------book page break-----------

Now let us try this question:

--------- Reference to question: 1bc6577e-462d-4d06-8952-8e5d211c4aa1 ---------

-----------book page break-----------

III. Rapid Practice

Use the following rapid practice widget to see if your understanding of co-prime numbers is complete or not. To use this practice you may need to compute $GCD$ of two numbers using a more efficient method. If you are not familiar with , we recommend you read it first.