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 2 numbers a in the set \{1,2,3\dots9400\} such that a^2-a is divisible by 10000

HINT

Use Modular arithmetic and concepts of coprime numbers

SOLUTION

we know

10000=2^4*5^4

In order for 10000 to divide a^2-a both 2^4 and 5^4 must divide a^2-a

Write a^2-a=a(a-1)

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

That means either

2^4 divides a and 5^4 divides (a-1)

or

2^4 divides a-1 and 5^4 divides a

Case-1

2^4 divides a and 5^4 divides (a-1)

AS 5^4=625 divides a-1 we can write

a-1=625k for some integer k

\Rightarrow a=625k+1

Now 2^4=16 divides a=625k+1

Note that 16 divides 624 hence 16 will also divide 624k

We can write 625k+1=624k+k+1

As 16 divides 625k+1=624k+k+1 so it must divide k+1

\Rightarrow k is among the numbers T=\{15,31,47\dots\}

For k=15 we get a=625*15+1=9376

For k=31 the value of a is 19376>9400

So from 31 onward none of the elements of T is acceptable

So in this case the only possible value of a is 9376

Case-2

2^4 divides a-1 and 5^4 divides a

As 5^4=625 divides a so a=625k for some integer k

\Rightarrow a-1=625k-1

Now 2^4=16 divides a-1

Write 625k-1=624k+k-1

As in the last case we can argue that 16 divides 624 so it must divide k-1

So K must be from the set U=\{1,17,33\dots\}

For k=17 , a=10625>9400 so any value of k greater or equal 17 does not count

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

So a=625

So 625 & 9376 these are the only 2 values that a can take

PROBLEM

Show that there are exactly 2 numbers a in the set \{1,2,3\dots9400\} such that a^2-a is divisible by 10000

HINT

Use Modular arithmetic and concepts of coprime numbers

SOLUTION

we know

10000=2^4*5^4

In order for 10000 to divide a^2-a both 2^4 and 5^4 must divide a^2-a

Write a^2-a=a(a-1)

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

That means either

2^4 divides a and 5^4 divides (a-1)

or

2^4 divides a-1 and 5^4 divides a

Case-1

2^4 divides a and 5^4 divides (a-1)

AS 5^4=625 divides a-1 we can write

a-1=625k for some integer k

\Rightarrow a=625k+1

Now 2^4=16 divides a=625k+1

Note that 16 divides 624 hence 16 will also divide 624k

We can write 625k+1=624k+k+1

As 16 divides 625k+1=624k+k+1 so it must divide k+1

\Rightarrow k is among the numbers T=\{15,31,47\dots\}

For k=15 we get a=625*15+1=9376

For k=31 the value of a is 19376>9400

So from 31 onward none of the elements of T is acceptable

So in this case the only possible value of a is 9376

Case-2

2^4 divides a-1 and 5^4 divides a

As 5^4=625 divides a so a=625k for some integer k

\Rightarrow a-1=625k-1

Now 2^4=16 divides a-1

Write 625k-1=624k+k-1

As in the last case we can argue that 16 divides 624 so it must divide k-1

So K must be from the set U=\{1,17,33\dots\}

For k=17 , a=10625>9400 so any value of k greater or equal 17 does not count

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

So a=625

So 625 & 9376 these are the only 2 values that a can take

Leave a Reply

Your email address will not be published. Required fields are marked *

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

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy
Cheenta

Cheenta Academy

Aditya Birla Education Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
JOIN TRIAL
support@cheenta.com
Menu
Trial
Whatsapp
ISI Entrance Solutions
ISI CMI Self Paced
magic-wandrockethighlight