Solving a system of congruent equations

Question

1.$$10x\equiv 34 \pmod{63}$$

2.$$11x\equiv 44 \pmod{64}$$

3.$$12x\equiv 54 \pmod{65}$$

How am I supposed to solve it? I know that use of the Chinese remainder theorem is not allowed in this case because 'x' doesn't appear solely in the equations.

after using some modular arithmetic I get:

1. $2x\equiv 9 \pmod 5$

2. $x\equiv 4 \pmod 2$

3. $5x\equiv 17 \pmod 7$

How do I continue?

Answer 1

Hint: $$10\times 19 \equiv 1 \pmod{63}$$ $$11\times 35 \equiv 1 \pmod{64}$$ $$12\times 38 \equiv 1 \pmod{65}$$

Answer 2

Since Math Lover hint "didn't ring a bell", here is hint n°2.

Remember these properties of modulo:

$$x\equiv y \pmod n \implies ax\equiv ay\pmod n$$ $$x\equiv y \pmod n \land x\equiv z\pmod n \implies y\equiv z\pmod n$$

Now, using these 2 equations:

$$10*19\equiv 1 \pmod {63} $$ $$10x\equiv 34 \pmod {63}$$

Find 2 ways to write:

$$10*19*x\equiv ? \pmod {63}$$

Doing the same with the other equations should help you to make x "appear solely in the equations"

Answer 3

Consider (1). We must find a number $a$ where $0\leq a\leq 62$ such that $10a\equiv 1\bmod 63$ in order to isolate $x$. By a lot of trial and error we find that $a=19$. Similarly, for (2) and (3) we find that $a=35$ and $a=38$. (Incidentally, this is what MathLover's hint alludes to.)

So now, having performed this multiplication, - we reduce the system to the following congruences $$x\equiv 34\cdot 19\equiv 16\bmod 63,$$ $$x\equiv 44\cdot 35\equiv 4\bmod 64,$$ $$x\equiv 54\cdot 38\equiv 37\bmod 65.$$

Now, since $63,64,65$ are mutually co-prime, we may apply Chinese remainder theorem which I shall do in a bit. First, try having a go yourself.

Answer 4

First thing to ask is whether you can simplify any of the congruences. We have that if $ac\equiv bc \pmod{m}$ and $\gcd(m,c)=d$, (i.e., if $ac\equiv bc \pmod{m'c}$, where $m=m'c$) then we can simplify by dividing through in the congruence by $d$ thus: $$a\equiv b \pmod{\frac{m}{d}}\tag{1}$$ If you check this $\gcd$ condition you find you cannot do this for any of your congruences.

If $\gcd(a,m)=1$, then the linear congruence $$ax\equiv b \pmod{m}\tag{2}$$ has a unique solution. That is only one of $0$, $1,\dotsc,m-1$ makes the product $ax$ congruent $b$ modulo $m$. As a special case if we let $b=1$ we get $$ax\equiv 1 \pmod{m}\tag{3}$$ with the unique solution of this congruence being termed the reciprocal of $a$ modulo $m$.

Now you should note that $\gcd(10,63)=\gcd(11,64)=\gcd(12,65)=1$, and so each of the congruences has a unique solution of $(3)$ thus: \begin{align*} 10\cdot 19 &\equiv 1 \pmod{63}\\ 11\cdot 35 &\equiv 1 \pmod{64}\\ 12\cdot 38 &\equiv 1 \pmod{65} \end{align*} Now you have the inverses $19$, $35$ and $38$ respectively, you can simply multiply the original congruences by them to isolate $x$ thus: \begin{align*} 10\cdot 19x &\equiv 1\cdot x \equiv 34\cdot 19 \equiv 16\pmod{63}\\ 11\cdot 35x &\equiv 1\cdot x \equiv 44\cdot 35 \equiv 4\pmod{64}\\ 12\cdot 38x &\equiv 1\cdot x \equiv 54\cdot 38 \equiv 37\pmod{65} \end{align*} Since the moduli are pairwise coprime, (i.e., $\gcd(63,64)=\gcd(63,65)=\gcd(64,65)=1$), you can use the Chinese Remainder Theorem to uniquely solve your system modulo the product of the moduli, $M=63\cdot64\cdot65=262080$. Let $M_i=\frac{M}{m_i}$, where $m_1=63$, $m_2=64$, $m_3=65$. Then $M_1=64\cdot65=4160$, $M_2=63\cdot65=4095$, $M_3=63\cdot64=4032$. Now each $M_i$ has a unique reciprocal, $M_i'$, modulo $m_i$, since $\gcd(M_i,m_i)=1$, so letting $$x=16\cdot M_1M_1'+4\cdot M_2M_2'+37\cdot M_3M_3'$$ then since $M_i\equiv0\pmod{m_k}$ if $i\neq k$, we have

\begin{align*} x &\equiv 16\cdot M_1M_1'\equiv 16\pmod{63}\\ x & \equiv 4\cdot M_2M_2'\equiv 4\pmod{64}\\ x &\equiv 37\cdot M_3M_3'\equiv 37\pmod{65} \end{align*}

So we need to solve for the modular inverses $M_i'$ \begin{align*} 4160\cdot M_1' &\equiv4160\cdot 32\equiv 1\pmod{63}\\ 4095\cdot M_2' &\equiv4095\cdot 63\equiv 1\pmod{64}\\ 4032\cdot M_3' &\equiv4032\cdot 33\equiv 1\pmod{65} \end{align*} so our solution is then $$x=16\cdot 4160\cdot 32+4\cdot 4095\cdot 63+37\cdot 4032\cdot 33=8084932$$ and so $$x\equiv8084932\equiv 222532\pmod{262080}$$ Therefore $x=222532$ is the smallest solution to the set of congruences.