Modular arithmetic $(3n – 2)x + 5n \equiv 0 \pmod{9n-9}$

elementary-number-theorymodular arithmetic

$(3n – 2)x + 5n \equiv 0 \pmod{9n-9}$

I know that the congruence has a solution if $gcd((3n – 2), (9n -9)) \mid -5n$ And it seems to have solution because $gcd((3n – 2), (9n -9)) = 1$

I tried with several $x$’s in the equation $(3n-2)x +5n$ but couldn’t found one that would be divisible by $(9n -9)$

I’m lost. Before, I posted a similar problem Modular arithmetic $(2n+1)x \equiv -7 \pmod 9$
The similarity I see is that in the module the number $9$ Appears again. Still I don’t know if it’s useful.

Thanks in advance.

Best Answer

$\begin{align} {\bf Hint}\ \bmod 9(n\!-\!1)\!:\ \, &3n\!-\!2\:\! =\:\! \overbrace{ 1\,+\,\color{#0a0}\epsilon}^{\large 1\ +\ \color{#0a0}{3(n-1)}\!\!\!\!\!\!\!\!\!\!}\ \ \ \& \ \ \color{#c00}{\varepsilon^2 \equiv 0} \ \ \ \rm so\\[.3em] &\!\!\dfrac{1}{3n\!-\!2}\equiv\dfrac{1-\color{#c00}{\epsilon^2}}{1+\epsilon\ \ }\equiv 1-\color{}\epsilon \equiv 4\!-\!3n\end{align}$

$\ $ which implies that: $\ \ \ \,(3n\!-\!2)\,x\:\!\equiv\:\! a\, \iff\, x\equiv (4\!-\!3n)\,a$

Remark $ $ The same works for higher powers $\color{#c00}{\epsilon^k\equiv 0}\,\Rightarrow\, 1+\epsilon\,\mid\, 1 = 1-\color{#c00}{\epsilon^k}.\,$ This simple inversion method is one of the prototypical methods discussed in this answer on "simpler multiple" methods. More generally this is a special case of successive approximations schemes such as Hensel lifting of solutions, or general Newton's methods.

Or we can invert using the augmented-matrix form of the extended Euclidean algorithm.

$\begin{eqnarray} [\![1]\!]&& && &\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! f := 9n\!-\!9\ =&\, \left<\,\color{#c00}1,\,\color{#0a0}0\,\right>\quad\ \ {\rm i.e.}\ \ \ \ \ \ f\, =\ \color{#c00}1\cdot f\, +\, \color{#0a0}0\cdot g\\ [\![2]\!]&& &&\qquad\ \ \, g :=3n\!-\!2 &\!\!=&\, \left<\,\color{#c00}0,\,\color{#0a0}1\,\right>\quad\ \ {\rm i.e.}\ \ \ \ \ \ g\, =\ \color{#c00}0\cdot f\, +\, \color{#0a0}1\cdot g\\ [\![3]\!]&=&[\![1]\!]-3[\![2]\!]\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &&\qquad\qquad\ \ \ \ \ \ \ \ \,{-}3 \,&\!\!=&\, \left<\,\color{#c00}1,\,\color{#0a0}{-3}\,\right>\ \ \ {\rm i.e.}\ \ \ {-}3\, =\, \color{#c00}1\cdot f\,\color{#0c0}{-\,3}\cdot g\\ [\![4]\!]&=&[\![2]\!]+n[\![3]\!]\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &&\qquad\qquad\qquad\ {-}2 \,&\!\!=&\, \left<\,\color{#c00}{n},\,\color{#0a0}{1\!-\!3n}\,\right>\\ [\![5]\!]&=&[\![4]\!]\ -\ [\![3]\!]\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &&\qquad\qquad\qquad\ \,&\!\!\!\!\!\! 1\ =&\, \left<\,\color{#c00}{n\!-\!1},\,\color{#0a0}{4\!-\!3n}\,\right>\\ \end{eqnarray}$

Hence the prior line implies: $ \ \ \underbrace{1\:\! =\, (\color{#c00}{n\!-\!1})f + (\color{#0a0}{4\!-\!3n})g}_{\large\text{Bezout equation for }\!\gcd(f,g)}\:\!\Rightarrow\, \smash{\bbox[7px,border:1px solid #c00]{ 1\equiv (4\!-\!3n)g\,\pmod{\!f}}} $

Related Question