Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$ Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$.
Hello. I am working on a review sheet for my test tomorrow and I am stuck on this question. 
I found earlier that all integers $x$ such that $19x-12$ is divisible by $23$ is 
$x\equiv 20 \pmod{23}$, but I am not sure if this helps.
 A: It seems that you should solve the rest congruence $5x\equiv 1(\operatorname{mod} 13)$ to the form $x\equiv a (\operatorname{mod} 13)$ and then use 
Chinese remainder theorem and a constructive algorithm to find the solution of a system of congruences.
A: Since $19\cdot17\equiv1\pmod{23}$, the second equation is equivalent to
$$
x\equiv 12\cdot17\pmod{23}
$$
or
$$
x\equiv 20\pmod{23}
$$
Similarly, the first equation is equivalent to
$$
x\equiv 8\pmod{13}
$$
because $5\cdot8\equiv 1\pmod{13}$.
Now the method with the Chinese remainder theorem can be applied.
A: Yes, $19x\equiv 12\pmod{23}$ is equivalent to $x\equiv 20\pmod{23}$. Similarly, $5x\equiv 1\pmod{13}$ is equivalent to $x\equiv 8\pmod{13}$.
So we want to solve the system of congruences $x\equiv 8\pmod{13}$, $x\equiv 20\pmod{23}$. In general to solve systems of linear congruences we use the machinery of the Chinese Remainder Theorem. But for a "small" problem like ours, one can find the answer by playing around. We want $20+23k$ to have remainder $8$ on division by $13$. We can try $k=0$ to $12$, or use more machinery.
We want $7+10k\equiv 8\pmod{13}$ or equivalently $10k\equiv 1\pmod{13}$. The inverse of $10$ modulo $13$ is $4$, so we want $k=4$. Thus the general solution is $20+4\cdot 23\pmod{(13)(23)}$.
A: If $x$ and $y$ both satisfy the condition, then $x-y$ is a multiple of $13$ and of $23$, therefore a multiple of $299 = 13 * 23$. It also works the other way around: if $x$ satisfies it, then so does $x+299k$. So if you find one, you've found them all.
To find one: from your finding, try numbers $x_k=20+23k$ (which satisfy the second part) and find out for which $k$ the number $x_k$ will satisfy the first part. For that you can simplify $x_k$ to a congruent mod 13 number, for example $20+10k$ or $-6-3k$. Once you find such $k$, $x_k$ is the one.
You might be also interested in Chinese remainder theorem.
