# Solve the following linear congruences [duplicate]

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 ?

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.

• What is number of elements of $N_{a,b}$ – Warrior Dec 1 '15 at 17:21
• The solution is unique modulo $999$, so in the range $[1,999]$, one and only one number satisfies the congruences. – Peter Dec 1 '15 at 17:23