For any integers $a, b$, let $N_{a,b}$ denote the number of positive integers $x<1000$ satisfying $x\equiv a\pmod{27}$ and $x\equiv b\pmod{37}$. Then find $N_{a,b}$.
progress: $x\equiv a\pmod{27}$ and $x\equiv b\pmod{37}$ implies
$x=27m+a$ and $x=37n+b$ for some integers $m,n$. For common sosultion, $27m+a=37n+b\implies 27m-37n=b-a$. Now $\gcd(27,37)=1$ sow there exists integers $u,v$ such that $27u+37v=1$.
Is it possible to solve using this relation ?
Thank u in advance
The numbers $u$ and $v$ can be found with the extended euclidean algorithm
$37=27\times 1+10$
$27=2\times 10+7$
$10=7\times 1+3$
$7=3\times 2+1$
Giving $1=7-3\times 2=7-(10-7)\times 2=3\times 7-2\times 10=3(27-2\times 10)-2\times 10=3\times 27-8\times 10=3\times 27-8\times (37-27)=11\times 27-8\times 37$
This gives the inverses : $27^{-1}=11 \pmod{37}$ and $37^{-1}=-8=19 \pmod {27}$
Now, the number $u=19\times 37\times a+11\times 27\times b$ satisfies $u\equiv a\pmod {27}$ and $u\equiv b\pmod{37}$. Taking $u$ modulo $27\times 37=999$ gives the smallest solution.