How Cheenta works to ensure student success?
Explore the Back-Story

# TESTING THE CONCEPT OF COPRIME NUMBERS | CMI 2015 PART B PROBLEM-3

## PROBLEM

Show that there are exactly numbers in the set such that is divisible by

## HINT

Use Modular arithmetic and concepts of coprime numbers

## SOLUTION

we know

In order for to divide both and must divide

Write

Note that and are coprime numbers so they can not have any common divisors

That means either

divides and divides

or

divides and divides

## Case-1

divides and divides

AS divides we can write

for some integer

Now divides

Note that divides hence will also divide

We can write

As divides so it must divide

is among the numbers

For we get

For the value of is

So from onward none of the elements of is acceptable

So in this case the only possible value of is

## Case-2

divides and divides

As divides so for some integer

Now divides

Write

As in the last case we can argue that divides so it must divide

So must be from the set

For so any value of greater or equal does not count

So the only possible value that can take in this case is

So

So & these are the only values that can take

## PROBLEM

Show that there are exactly numbers in the set such that is divisible by

## HINT

Use Modular arithmetic and concepts of coprime numbers

## SOLUTION

we know

In order for to divide both and must divide

Write

Note that and are coprime numbers so they can not have any common divisors

That means either

divides and divides

or

divides and divides

## Case-1

divides and divides

AS divides we can write

for some integer

Now divides

Note that divides hence will also divide

We can write

As divides so it must divide

is among the numbers

For we get

For the value of is

So from onward none of the elements of is acceptable

So in this case the only possible value of is

## Case-2

divides and divides

As divides so for some integer

Now divides

Write

As in the last case we can argue that divides so it must divide

So must be from the set

For so any value of greater or equal does not count

So the only possible value that can take in this case is

So

So & these are the only values that can take

This site uses Akismet to reduce spam. Learn how your comment data is processed.