Cheenta
How 9 Cheenta students ranked in top 100 in ISI and CMI Entrances?
Learn More

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

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