Find the smallest natural $n$ satisfying three congruences

Question

I gotta find the smallest natural number $n$ that satisfies the following conditions: $$ 3^2|n, \qquad 4^2|(n+1), \qquad 5^2|(n+2). $$

How would I go about tackling this problem? I need some assistance in how and where to begin.

3 Expressions

Answer 1

Using the Chinese remainder theorem and some computation, we can find that all $n\in{\mathbb N}$ satisfying the given conditions are $$ n=9\cdot16\cdot25\cdot k+2223, \qquad\mbox{ or }\qquad n=3600k+2223. \tag{1} $$ The smallest positive integer of the form $(1)$ is $n=2223$.

But the general solution $(1)$ is not really needed if we only want the smallest $n$ satisfying the given congruences. We can find the smallest such $n$ by applying the Chinese remainder theorem to two moduli first, e.g. to $16$ and $25$. Thus we can first find that if $16|(n+1)$ and $25|(n+2)$, then $n$ must have the form: $$ n=16\cdot25\cdot m+223, \qquad\mbox{ or }\qquad n=400m+223. \tag{2} $$ Indeed, $400m+225$ is a multiple of $25$, while $400m+224$ is a multiple of $16$. Let's write down a few natural $n$ satisfying $(2)$: $$ 223, 623, 1023, 1423, 1823, 2223, 2623, \ldots $$ Now we simply check that, among the above numbers, the smallest $n$ divisible by $9$ is $n=2223$.