Try these problem by yourself first:
1. Given relatively prime integers $a, b, c$, if I tell you any three numbers $i, j, k$, can you tell me an integer $N$ such that all three holds simontaneously: $$ N \equiv i \mod a$$ $$N \equiv j \mod b$$ $$N \equiv k \mod c$$ ? Can you always give me such $N$ ?
As a concrete example, can you tell me a number $N$ such that $$N \equiv 5 \mod 7$$ $$N \equiv 2 \mod 5$$ $$N \equiv 10 \mod 11$$ ?
Can you generalize ?
- When $N$ varies from $0$ to $5*7*11$, how does $$\{ N \mod 7 \}, \{ N \mod 5 \}, \{N \mod 11 \}$$ varies ?
Nice observation, but this is basically Chinese Remainder Theorem. (See the handout here for some nice and hard problems regarding this)
The $\mod p$ part is handled by Fermat's theorem, but the $\mod 3$ part is easily handled by observing $$ 2^{odd} \equiv 2 \mod 3$$ and $$1^{odd} \equiv 1 \mod 3$$.
In case you're feeling bad this turned out to be trivial, try this fun one if you didn't see it before: $2n$ divideds $\phi(a^n+1)$ for any integer $a, n$ with $gcd(a,n) = 1$