simultaneous linear congruence- Chinese remainder theorem

Question

find a integer r that satisfies both congruence

r ≡ 3 mod 1293 and r ≡ 0 mod 3936

im stuck on this question my method was using Chinese remainder theorem.

first found the gcd(1293,3936) = 3

then i checked if 3 is divisible by (3-0) which it is

then i found the lcm(1293,3936) = 1696416 which should be r

but when i sub back into the original i dont get an integer. im not sure what im doing.

Answer 1

First divide the first congruence by $3$.

Using the existence construction for the Chinese remainder theorem, we get:

$431(-1105)+3936(121)=1\implies 0×431(-1105)+1×3936(121)=1428768$ is a solution.

Answer 2

First observe that $r \equiv 3 \bmod 1293$ if and only if $r = 3k$ with $k \equiv 1 \bmod 431$. Similarly, $r = 3k \equiv 0 \bmod 3936$ if and only if $k \equiv 0 \bmod 1312$. Thus $k$ is a multiple of $1312$, say $1312n$, congruent to $1$ modulo $431$. In order to find $n$, first solve the equation $1312n \equiv 1 \bmod 431$. Since $1312 \equiv 19 \bmod 431$, this equation reduces to $19n = 1 \bmod 431$, which admits $n = 363$ as a solution. Thus $3 * 363 * 1312 = 1428768$ is a solution to your question.