Question

How many positive integers $N$ from 1 to 5000 satisfy both congruences, $N\equiv 5\pmod{12}$ and $N\equiv 11\pmod{13}$?

Answer 1

Use the Chinese remainder theorem. Suppose we set
`N=5\cdot13+11\cdot12`. Then clearly taken modulo 12, the second term vanishes, and incidentally
`5\cdot13\equiv65\equiv5\pmod{12}`; taken modulo 13, the first term vanishes, but the second term leaves a remainder of 2. To counter this, we can multiply the second term by the inverse of 12 modulo 13, which is 12 since
`12^2\equiv144\equiv11\cdot13+1\equiv1\pmod{13}`.

So, we found that
`N=5\cdot13+11\cdot12^2=1649`, but the least positive solution is
`1649\equiv89\pmod{\underbrace{156}_(12\cdot 13)}`, and in general we can have
`N=89+156k` for any integer
`k`.

Now, since
`5000=32\cdot156+8`, or
`4992=32\cdot156`, we know that there are 32 possible integers
`N` that satisfy the congruences.