Path needed for solving these linear equations in Zn (my example Z105)

Question

So these are two equations : $$49x \equiv 21 \pmod {105}$$ $$64x \equiv 21 \pmod {105}$$

I should find the multiplicative inverse of $64$ and then $49$ that gets the result of $1$

so....

In the first equation i know that the $\gcd(49, 21)$ is $7$ So reducing them, I have $7x \equiv 7 \pmod {105}$ and $105 = 15 \times 7$ here I get lost!!

---

In the second equation I know that $64$ and $21$ are coprime with each other, so euclidean algorithm, bezout identity, smth like 64v + 21w = 1 right.. and if I found V I basically found the x... but I get lost somewhere...

first I do the $\gcd(105, 64)$ then with bezout identity I want to find v and w such that = $1$ and I have $25$ for the bigger term and $-41$ for the smaller term...

but $64 x 25 + 21(-41)$ doesn't equal to $1$

again,, lost... connection not found!! :D

please help... maybe i chose the wrong direction, and math doesn't do for me!

Answer 1

Note that you could combine these equations and get:

$15x\equiv0 (\mod 105)$ which would reduce your initial equations to $4x\equiv21 (\mod 105)$

From here, you could use the Chinese Remainder Theorem for one idea or look at $21+105k$ and find a multiple of 4 there.

$21+3*105= 21+315 = 336 = 4 * 84$

Thus, try $x\equiv84 (\mod 105)$ as one solution.

Answer 2

The inverse of $64$ modulo $105$ can be found with the Euclidean algorithm: \begin{align} 105&=64\cdot 1+41\\ 64&=41\cdot 1+23\\ 41&=23\cdot 1+18\\ 23&=18\cdot 1+5\\ 18&=5\cdot 3+3\\ 5&=3\cdot 1+2\\ 3&=2\cdot 1+1 \end{align} Thus \begin{align}\def\c#1{\color{red}{#1}} 1&=\c{3}-\c{2}\\ &=\c{3}-(\c{5}-\c{3})=(-1)\cdot\c{5}+2\cdot\c{3}\\ &=(-1)\cdot\c{5}+2(\c{18}-3\cdot\c{5})=(-7)\cdot\c{5}+2\cdot\c{18}\\ &=-7(\c{23}-\c{18})+2\cdot\c{18}=(-7)\cdot\c{23}+(-5)\cdot\c{18}\\ &=(-7)\cdot\c{23}+(-5)(\c{41}-\c{23})=(-2)\cdot\c{23}+(-5)\cdot\c{41}\\ &=(-2)(\c{64}-\c{41})+(-5)\cdot\c{41}=(-2)\cdot\c{64}+(-3)\cdot\c{41}\\ &=(-2)\cdot\c{64}+(-3)(\c{105}-\c{64})=\c{64}+(-3)\cdot\c{105} \end{align} and it turns out that the inverse is $64$.

Therefore, from the second equation, we get that $$ x\equiv 64\cdot21\equiv1344\equiv84\pmod{105} $$ Now $$ 49\cdot 84=4116\equiv21\pmod{105} $$ and you're done.