Modular arithmetic $(2n+1)x \equiv -7 \pmod 9$ Find a solution $(2n+1)x \equiv -7 \pmod 9$
I’m sure this is trivial but I still have doubts about it.
I know the equation has solution for certain $n \in \mathbb {Z}$. Actually I have tried a few and got a similar results (with Diophantine equations ). I wonder if there’s general solution for the equation without changing the n for an integer.
Thanks in advance.
 A: Hint $\,\bmod 9\,$ invertibles have form $\,2^{\large n}$ so $\,2^{\large n} x\equiv 2 \iff x \equiv 2^{\large\:\! 7-n},\,\ n = 0,1,2,\ldots,5 $
Example $\ $ For $\,n = 2\,$ the above says that $\, 2^{\large 2} x\equiv 2\iff x\equiv 2^{\large 5}\equiv 5.\,$ Indeed  $\,2^{\large 2} 5\equiv 2\,\color{#c00}\checkmark$
Remark $\ $ Since $\,-7\equiv 2\,$ is invertible $\bmod 9\,$ so too is its factor $\,a := 2n\!+\!1.\,$ Or, more explicitly, $\,ax\equiv 2\,\iff ax\,2^{-1}\equiv 1\iff a^{-1}\equiv 2^{-1}x\equiv 5x$
That every invertible has form $\,2^{\large n}$ follows because $\,2\,$ is a primitive root
$\bmod 3^{\large 2}\,$ (generally a p.r. $\,g \bmod p\,$ persists as a p.r. $\bmod p^k\,$ except if $\, g^{\large p-1}\!\equiv 1\pmod{\!p^2};\,$ where instead $\,g\! +\! p\,$ works). 

Directly: $\,a\,$ invertible $\!\bmod 9\iff a\,$ invertible $\!\bmod 3\iff a = \pm1 + 3j,\,$ so
$\!\bmod \color{#c00}9\!:\,\ ax = (\pm1 + 3j)x \equiv 2\iff x\equiv \dfrac{2}{\pm1 + 3j} \equiv \dfrac{2(1-\color{#c00}9j^2)}{\pm1 + 3j\ \ } \equiv 2(\pm1 -3j)$
Example $\ \  \ \ \ \ a  = 1+3\iff x \equiv 2(1-3)\equiv 5,\,$ same as above
A: Note that $-7 \equiv 2$ is invertible modulo 9, so there will be a solution if and only if
$$ 2^{-1} (2n+1) x \equiv 1 \pmod{9}.$$
For this to work, we need $(2n+1)$ to be a unit modulo 9 (since its inverse is given by $2^{-1}x$). The only non-units modulo 9 are 0, 3, and 6, so the equation will have a solution if and only if
$$ 2n+1 \not\equiv 0,3,6 \pmod{9}.$$
From there you can simplify and solve.
A: $2n+1=6k+1$ or $2n+1=6k+5$, where $k\in\mathbb Z$.
If $2n+1=6k+1,$ so $n=3k$ and
$$(6k+1)x\equiv-7(\mod9)$$ it's
$$(6k+1)(3k+1)x\equiv-7(3k+1)(\mod9)$$ or
$$x\equiv-7(n+1)(\mod9).$$
Can you end it now?
A: For $ax \equiv b \pmod{m}$ to have a solution, the necessary and sufficient condition is that the $\gcd(a,m) \mid b$. With this, we get $\gcd(2n+1,9) \mid 2$ (since $-7 \equiv 2 \pmod{9}$).
The possible values of $\gcd(2n+1,9)$ are $1,3,9$. But the only value that can divide $2$ is $\gcd(2n+1,9)=1$. Thus it will have a solution for all $n \in \Bbb{Z}$ such that
$$\gcd(2n+1,9)=1.$$
A: $9$ is not prime so it has $0$ divisors and you cant solve $3x \equiv k\pmod 9$ unless $k$ is a multiple of $3$.
Basically if $\gcd(m, n) = 1$ there will always be a solution (and only one solution) to $mx \equiv 1\pmod n$.  We can notate that solution as $m^{-1}$. ( So for example $5^{-1} = 2\pmod 9$ because $2*5 \equiv 1 \pmod 9$.
So for any $mx \equiv k \pmod n$ we can do $m^{-1}mx \equiv m^{-1}k\pmod n$ and so $x \equiv m^{-1}k\pmod n$.  So in your example if $2n +1 = 5$ we could solve $5x\equiv -7\pmod 9$ so $2*5x \equiv x \equiv 2*(-7)\equiv -14\equiv -5 \equiv 4\pmod 9$.  (And indeed $4*5 \equiv -7\pmod 9$).
But if $\gcd(m,n) \ne 1$ this does not follow unless $k$ is a multiple of $\gcd(m,n)$.   But if $k$ is a multiple of $\gcd(m,n)$ we can solve. 
.....
To put this all in perspective these are actually just a restatement of Bezouts lemma.
$mx \equiv k \pmod n$ is solveable if and only if there if is an integer $w$ so that $mx + wn = k$ which is solveable if and only if $k$ is a multiple of $\gcd(m,n)$.
So to solve $(2n + 1)x \equiv -7\pmod 9$: as $-7$ is not a multiple of an factor of $9$ other than $1$, this will only be solvable if $\gcd(2n+1, 9)= 1$.
So we may if and only if $2n+1$ is not a multiple of $3$.  Or in other words if and only if $2n+1 \not \equiv 0\pmod 3$ or $2n\not \equiv -1\pmod 3$ or $n \not \equiv 1\pmod 3$.
..... so final answer .....
For there to be solutions we can't have $n\equiv 1\pmod 3$. In other words we cant have $n\equiv 1,4,7\pmod 9$.
So we can have solutions if $n \equiv 0,2,3,5,6,8 \pmod 9$.
In those case $2n+1 \equiv 1,2,4,5,7,8\pmod 9$.
We can find $(2n+1)^{-1}\mod 9$ for those values.
$1*1 = 1; 2*5\equiv 1; 4*7\equiv 1; 5*2\equiv 1; 7*4\equiv 1; 8*\equiv 1\pmod 9$ so $(2n+1)^{-1}\equiv 1,5,7,2,4,8\pmod 9$ when $n \equiv 0,2,3,5,6,8\pmod 9$ respectively.
So solution to $(2n+1)x \equiv -7 \equiv 2 \pmod 9$ is $x\equiv (2n+1)^{-1}*2 \pmod 9$.
So if $n \equiv 0,2,3,5,6,8\pmod 9$ then $x \equiv (2n+1)^{-1}*2 \equiv 1*2,5*2,7*2,2*2,4*2, 8*2 \equiv 2,1,5,4,8,7\pmod 9$ respectively.
A: If $\quad(2n+1)x\equiv -7\pmod 9\quad$ then $\quad x\equiv 2(n^3+n+1)\pmod 9$
Note: Found it by hand extending from M.Rozenberg answer. We have $(4n+1)$ or $(4n+3)$ depending on divisibility of $n$ by $3$. I replaced then the constant by introducing a term in $n^3$. Can we find this result directly using extended euclidean algorithm or something similar, rather than brute force ?
A: \begin{align}
   (2n+1)x &\equiv 2 \pmod 9 \\
   5(2n+1)x &\equiv 1 \pmod 9 \\
   (10n + 5)x &\equiv 1 \pmod 9 \\
   (n-4)x &\equiv 1 \pmod 9 \\
   n-4 &\equiv x^{-1} \pmod 9 \\
   n &\equiv 4 + x^{-1}
\end{align} 
\begin{array}{c}
   x & n \equiv x^{-1} + 4 \\
\hline
   1 & 5 \\
   2 & 0 \\
   3 & \text{No solution.} \\
   4 & 2 \\
   &\text{etc.}
\end{array}
A: Since $2n + 1$ 'cycles through' the modulo $9$ residues, the problem is reduced to solving
$$\tag 1 x'x \equiv 2 \pmod 9$$
This is equivalent to $x'x = 9k +2$ and we need only look for solutions
$$ 0 \le x' \lt 9 \text{ and } 0 \le x \lt 9$$
We represent both $x'$ and $x$ in $\text{base-}3$ format,
$$\tag 2  x' = a' + b'3 \text{ and } x = a + b3 \quad \text{with } a',b',a,b \in \{0,1,2\}$$
Multiplying,
$$ x'x = a'a + (a'b+ab')3 + bb'3^2$$
Since $a'a + (a'b+ab')3 \le 28 \lt 29 = 2 + 3 \times 9$, we segment the work into 3 parts.
Part 1:  $a'a + (a'b+ab')3 = 2$
$\quad$ Ans: [$x' = 1$ and $x = 2$] OR [$x = 1$ and $x' = 2$]
Part 2:  $a'a + (a'b+ab')3 = 11$
$\quad$ Ans: [$x' = 4$ and $x = 5$] OR [$x = 4$ and $x' = 5$]
Part 3:  $a'a + (a'b+ab')3 = 20$
$\quad$ Ans: [$x' = 7$ and $x = 8$] OR [$x = 7$ and $x' = 8$]
We only work out the details for Part 3:
Since $3 \nmid 20$, $\,3 \nmid 19$ and $3 \nmid 16$, if we have any solutions at all we must have
$\quad a'a = 2$
$\quad (a'b+ab') = 6$
If we set $a' = 2$ and $a = 1$ we get $2b + b' = 6$. So $b = 2$ and $b' =2$. So $x' = 2 + 2 \times 3 = 8$ and $x = 1 + 2 \times 3 = 7$. Up to an interchange, there can be no other solutions.
