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