Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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)}$.

Answer 4

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.