1

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.

Octavio Berlanga
  • 452

8 Answers8

2

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

Bill Dubuque
  • 272,048
  • 1
    I was intrigued by your claim that all invertible elements of integers modulo $9$ have the form $2^n$. I don't doubt it -- it's easily verified by computation -- but I'm wondering if it's just a random fact you know or part of a more general rule -- it seems it's also true for mod $25$ but not $49$ – J. W. Tanner Aug 06 '19 at 20:41
  • @J.W.T Yes, I appended a remark on primitive roots. – Bill Dubuque Aug 06 '19 at 21:16
  • Thank you for the appendix explaining why $2$ is a primitive root modulo $9$ and $25$ (it is modulo $3$ and $5$, and the exception criterion is not met) but not $49$ (it is not modulo $7$ ;+) +1 – J. W. Tanner Aug 06 '19 at 22:26
1

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.

desiigner
  • 685
  • 3
  • 16
1

$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?

Michael Rozenberg
  • 194,933
1

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.$$

J. W. Tanner
  • 60,406
Anurag A
  • 41,067
1

$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.

fleablood
  • 124,253
1

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 ?

zwim
  • 28,563
  • Hmmm, didn't even think about a general formula but if $n =1$ you have $x\equiv 2(1^3+ 1 + 1) \equiv 6\pmod 9$ but $(21+1)6 \equiv 0\pmod 9$. You do* need to stated that $2n+1\not \equiv 0\pmod 3$. Otherwise your formula seems to work. – fleablood Aug 06 '19 at 22:32
  • Note that I assume first equation verified, which eliminates de facto cases $n=1,4,7\pmod 9$, which was abundantly dealt with in other answers. I was only interested in inverting polynomial $(2n+1)$ in the favorable cases. – zwim Aug 06 '19 at 22:38
  • @fleablood Actually there is a linear formula using the residue mod $3$ - see the last half of my answer. – Bill Dubuque Aug 06 '19 at 23:27
  • As $2n+1\not \equiv 0\pmod 3$ we know $(2n+1)^6\equiv 1 \pmod 9$ so $(2n+1)^5\equiv (2n+1)^{-1}$ but we can make simpler. $2n+1\equiv 3k \pm 1 \pmod 9$ and $(3k\pm 1)^5\equiv 15k \pm 1\equiv 6k\pm 1$. To put this in terms of $n$, $2n+1\equiv 3k \pm 1$ so $2n\equiv 3k,3k-2$ so $n\equiv 10n\equiv 15k,15k-10\equiv 6k,6k-1$ so $(2n+1)^{-1}\equiv n+1$ if $n\equiv 0,6,3$ and $(2n+1)^{-1}\equiv n$ if $n\equiv 8,5,2$. Not sure that makes anything easier. Probably easiest to just say $(3k\pm 1)^{-1}\equiv (6k\pm 1)$ and $(3k\pm 1)(6k\pm 1)\equiv 18k^2 \pm 9k + 1\equiv 1\pmod 9$. – fleablood Aug 07 '19 at 00:16
0

\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}

Steven Alexis Gregory
  • 26,769
0

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.

CopyPasteIt
  • 11,366