Problem 1

Let

m

and

n

be positive integers with

1 \le m < n

. In their decimal representations, the last three digits of

1978^m

are equal, respectively, to the last three digits of

1978^n

. Find

m

and

n

such that

m+n

has its least value.

Step 2 of 8: Split the modulus with the Chinese Remainder Theorem

Previous step Next step

In plain words

Working mod 8 and mod 125 separately is much easier than mod 1000 directly.

1000 = 2^3\cdot 5^3 = 8\cdot 125,\qquad \gcd(8,125)=1

Detailed analysis

Since $8$ and $125$ are coprime, the condition $1978^m\left(1978^{\,n-m}-1\right)\equiv 0 \pmod{1000}$ splits into two independent conditions, one modulo $8$ and one modulo $125$ .