Integer solution to multiple modular arithmetic equations

Question

So i understand how to do this when it is just x, but now with multiples of x I am a little confused, and there's no example in my textbook of this. I just need a push in the right direction for how to get started.

Find an integer x so that:

a. $3x\equiv2\pmod5$ and $4x\equiv5\pmod7$

b. $7x\equiv11\pmod9$ and $3x\equiv22\pmod{35}$

Answer 1

Because $2\cdot 3 = 6$ and $6\equiv 1\bmod 5$, we have that $$3x\equiv 2\bmod 5\iff 2\cdot(3x)\equiv 2\cdot (2)\bmod 5\iff 6x\equiv 4\bmod 5\iff x\equiv 4\bmod 5$$ See if you can find the right multiplication to do for the other three congruences :)

In general, if you're solving $ax\equiv b\bmod m$ and $\gcd(a,m)=1$, you'll want to look for some $c$ to multiply both sides by to get $x$ on its own. In other words, you're looking for a $c$ such that $ac\equiv 1\bmod m$. But this is equivalent to finding a $c$ and $d$ such that $$ac+dm=1$$ which is doable by Bezout's identity / extended Euclidean algorithm.

Answer 2

To solve the simultaneous equations, you will need the Chinese Remainder Theorem.
Given \begin{align*} x&\equiv a_1 \mod n_1\\ x&\equiv a_2 \mod n_2 \end{align*} such that $n_1$ and $n_2$ are coprime, then find $c,d$ such that $$cn_1+dn_2=1,$$ then $$x=a_1n_2d+a_2n_1c.$$ See that \begin{align*} x=a_1n_2d+a_2n_1c &\equiv a_1\mod n_1\\ &\equiv a_2\mod n_2 \end{align*} since $dn_2\equiv1\mod n_1$ and $cn_1\equiv1\mod n_2$.

Now, work out $c$ and $d$ and also, find $a_1$ and $a_2$ using the extended Euclidean algorithm.

Answer 3

$$3x\equiv 2\pmod 5\\ \implies 2\cdot 3x\equiv 6x\equiv x\equiv 2\cdot 2\equiv 4\pmod 5$$

Take this farther like so:

$$4x\equiv 5\pmod 7\\ 2\cdot4x\equiv x\equiv 2\cdot5\equiv 3\pmod 7$$

Find the number $\mod 35$ where these congruences coincide:

$$x\equiv 4\equiv 9\equiv \dots\equiv 24\pmod 5\\ x\equiv 3\equiv 10\equiv \dots\equiv 24\pmod 7\\ \implies x\equiv 24\pmod{35}$$

Answer 4

Here is how I think of problems of this type.

The relation ax≡b (mod c) is the same as the equation ax=b+cy where x,y∈Z. If I find the integer solutions to the equation, I would have found the integer solutions to the relation. One way to find integer solutions to the equation would be to introduce substitute variables.

Here is the crucial idea: the purpose for introducing substitute variables is to create a new system of equations so that when the system of equations were solved using substitution (I keep the coefficients integers during the substitution process), each of the original variables are expressed in terms of substitute variables. If this can be done, all I have to do is enumerate integer values for the substitute variables and I will get integer values for the original variables.

So as an example, given the equation ax-cy=b, first I factor out the greatest common divisor of a,c and b. Suppose〖 gcd〗⁡(a,c)=1. Which variable do I begin with? I would choose the equation with the smallest coefficient that is greater than 1. This coefficient is the coefficient of the substitute variable in the new equation. The other coefficients of the new equation are the remainders of the other coefficients from the equation if you divide the other coefficients with the selected coefficient. I proceed to add substitute variables until the coefficient of the last substitute variable is 1. At this point, I perform substitution right away to convert the new system in upper-echelon form. Then I repeat the search for the smallest coefficient that is greater than 1 and continue. I stop when all of the coefficients in the original system are 1. If there are no integer solutions, I get an equation with a coefficient greater than 1 or less than 1, and a right-hand constant that is greater than 0 or less than 0.

I use matrices to manually perform all computations.