Co-primes

Co-prime numbers are also known as Relatively prime numbers.

What are Co-prime numbers?

They are two natural numbers which doesn’t have a common factor other than 1, i.e. their H.C.F. is 1.
E.g. (8 and 9), (4 and 5).

Properties of Co-primes

Property 1: Consecutive numbers

• Two consecutive odd numbers are always co-prime numbers.
  E.g. (9 & 11), (15 & 17) etc.

• Three consecutive odd numbers are always co-prime numbers.
  E.g. (3, 5 & 7), (21, 23 & 25)

Property 2: As factors

How to find whether a number A is divisible by another number B?

We need to find two co-prime numbers, x and y such that B = x × y

If A is divisible by both x and y, then it is divisible by B.

E.g. Is 120 divisible by 24?
Now, 24 = 8 × 3 (8 and 3 are co-primes)
As 120 is divisible by both 8 and 3, so it must be divisible by 24 too.

In other words, if a number is divisible by two co-prime numbers, then the number is divisible by their product also.

We can extend this rule to more than 2 co-primes too.

So, if a number is divisible by more than two co-prime numbers, then the number is divisible by their product also.

E.g. Is 960 divisible by 60?
Now, 60 = 5 × 4 × 3 (5, 4 and 3 are co-primes)
As 960 is divisible by 5, 4 and 3, so it must be divisible by 60 too.

Property 3: Euler’s function

Euler’s function, ϕ(N) = the number of all co-primes to N, which are less than N.
If N = $a^p b^q c^r$ …..
ϕ(N) = N [1 − $\frac{1}{a}$] [ 1 − $\frac{1}{b}$] [1 − $\frac{1}{c}$] …..

Q. Example: Find the number of co-primes to 36, which are less than 36. OR
If p is relatively prime to 36 and p < 36. Find the number of possible values for p?

Explanation:

Property 4

Sum of all co-primes to N which are less than N = $\frac{N^2}{2}$ [1 − $\frac{1}{a}$] [ 1 − $\frac{1}{b}$] [1 − $\frac{1}{c}$] ….. = ($\frac{N}{2}$) ϕ(N)

Q. Find the sum of all co-primes to 18, which are less than 18.

Explanation: