Coincidences

It is required that $10^6=5^6*2^6$ divides $n^2-n=n(n-1)$ . Now $5^6=15625$ must divide one of the numbers $n$ and $n-1$ , while $2^6=64$ must divide the other. Thus one of the numbers $n$ and $n-1$ must be of the form $15625k$ , and it must be congruent to 1 or 63 modulo 64. Now $15625\equiv{9}\pmod{64}$ , so that $n-1=7*15625$ leads to the smallest number with the required property, $n=7*15625+1=\boxed{109376}$

Otto has a beautiful number theory solution that I highly suggest reading!

If you don't believe it, we can always check the answer computationally; here, in Python (<0.1 sec):

1
2
3
4
5
6
7
8

searching = True
current_int = 2
while searching:
    if current_int % 10**6 == current_int**2 % 10**6:
        print current_int
        searching = False
    else:
        current_int +=1