1. How many positive integers N from 1 to 5000 satisfy the congruence \(N \equiv 11 \pmod{13}\)?
2. How many positive integers N from 1 to 5000 satisfy both congruences, \( N\equiv 5\pmod{12}\) and \( N\equiv 11\pmod{13}\)?
1 -
N mod 13 = 11
N = 13m + 11, where m=0, 1, 2, 3.........etc.
5000 / 13 + 1 =385 integers that satisfy the congruence.
2 -
N mod 13 = 11
N mod 12 = 5, solve for N
Using "Chinese Remainder Theorem + Modular Multiplicative Inverse", we have:
N = 156m + 89, where m =0, 1, 2, 3........etc.
5000 / 156 + 1 =33 integers that satisfy both congruences.