# How to solve a linear congruence $8n+9\equiv 0\pmod{\!1163}$

Problem :

Solve in $$\mathbb N$$ :

$$8n+9\equiv 0\pmod{1163}$$

The mathematics give me : $$n=435+1163k$$ , $$k\in\mathbb N$$

$$1163$$ is a prime number

$$8n\equiv -9\pmod{1163}$$

$$8n\equiv 1154\pmod{1163}$$

I don't know any ideas to complete my work ?

I have to see your hints

• or multiply by $8^{1161} \equiv 727\pmod {1163}$
– zwim
Commented Nov 13, 2019 at 22:14
• Related to OP's earlier question. Commented Jan 7, 2020 at 21:16

$$8n\equiv 1154\;(mod \;1163)$$ $$\Rightarrow 4n\equiv577\; (mod \;1163)$$ $$\Rightarrow 4n\equiv-586\; (mod \;1163)$$ $$\Rightarrow 2n\equiv-293\; (mod \;1163)$$ $$\Rightarrow 2n\equiv870\; (mod \;1163)$$ $$\Rightarrow n\equiv435\; (mod \;1163)$$

• Thank you very much sir @lessili , but $x\equiv a\pmod{b}$ then $\frac{x}{n}\equiv \frac{a}{n}\pmod{b}$ ? Always ? Commented Nov 13, 2019 at 22:23
• Nice use of the oddness of the modulo. Do not be afraid of using \iff since $\gcd(2,1163)=1$ division by $2$ is ok (it would be nice you write it though).
– zwim
Commented Nov 13, 2019 at 22:23
• Not always just in this case because 1163 is odd so you can divide by 2 as much as you want. Commented Nov 13, 2019 at 22:25
• OK @lessili thanks again!😍 Commented Nov 13, 2019 at 22:28
• @Ellen I explain the idea behind this method in my answer. Commented Nov 13, 2019 at 23:14

Six ways to compute $$\!\bmod 1163\!:\ n\equiv \dfrac{-9}8\equiv -9 \cdot 8^{-1},\,$$ the unique root of $$\,8n\equiv -9$$.

$$\!\!\bmod 1163\!:\,\ n\equiv 3\left[\dfrac{-3}8\right] \equiv 3\left[\dfrac{1160}8\right]\equiv 3[145]\equiv 435\$$ by twiddling or Reciprocity below.

Inverse Reciprocity is essentially the key idea behind lone student's and J.W.T's answer, viz.

$$\!\!\bmod 1163\!:\,\ n \equiv \dfrac{-9}8\equiv \dfrac{-9+1163\color{#c00}k}8.\$$ To make the quotient exact we need $$\,k\,$$ such that

$$\!\!\bmod 8\!:\,\ 0\equiv -9\!+\!1163k\equiv -9\!+\!3k\!\iff\! \color{#c00}{k\equiv 3},\$$ so $$\ n \equiv \dfrac{-9\!+\!1163(\color{#c00}3)}8\equiv 435\pmod{\!1163}$$

This idea is also (implicitly) used in the first method above, i.e. $$\,1163\equiv \color{#0a0}3\pmod{\!8}\,$$ so clearly adding $$1163$$ to the numerator $$\color{#0a0}{-3}$$ makes the numerator divisible by $$\,8,\,$$ i.e. $$\,\color{#c00}{k=1}\,$$ works here (it is $$\,1/3\,$$ of the above $$\,\color{#c00}{k=3}\,$$ since there we factored out $$\,3\,$$ from the numerator $$-9).\,$$ In cases like this where small solutions exist for $$\,k\,$$ often we can "see" them quickly without explicitly solving the above linear congruence (e.g. by testing small values $$\,k\equiv \pm1,\pm2\,$$ etc, i.e. "twiddle" the numerator by adding small multiples of the modulus then testing if this yields an exact quotient). This is essentially an optimization of the Extended Euclidean Algorithm (when it takes two steps).

$$\!\!\bmod 1163\!:\,\ \dfrac{1}{4}\equiv\dfrac{1164}4\equiv 291\overset{\times\,\large\frac{\!-1}2}\Longrightarrow\: \dfrac{\!\!-1}8\equiv\dfrac{-291}2$$ $$\equiv\dfrac{872}{2}\equiv 436;\,$$ subtract $$\,1\,$$ to get $$\ \dfrac{\!-9}8$$

As above & here the freedom to choose $$\rm\color{#c00}{even}$$ residue reps $$\!\bmod\!$$ odds makes division by 2 easy:

$$\bmod 1163\!:\,\ n\equiv \dfrac{-9}{8} \equiv \dfrac{\color{#c00}{-1172}}8\equiv \dfrac{-293}2\equiv\dfrac{\color{#c00}{870}}2\equiv 435.\$$ Or, similar to lesseli's answer

$$\bmod 1163\!:\,\ n\equiv \dfrac{-9}{8}\ \equiv\ \dfrac{\color{#c00}{1154}}8\ \equiv\ \dfrac{577}4\equiv\dfrac{\color{#c00}{1740}}4\equiv435$$.

The key idea is: if the modulus $$m$$ is odd then $$\,2\mid a\,$$ or $$\,2\mid \color{#c00}{a\!\pm\!m},\,$$ so we can quickly divide by $$\,2\,$$ by choosing the $$\rm\color{#c00}{rep}$$ that is even. Iterating that we can easily divide by all powers of $$\,2\,$$ (e.g $$\,8\,$$ above). This is the idea in lessili's answer, and the 2nd way above. More generally, see below.

$$\!\!\bmod 1163\!:\ {-}n\equiv \dfrac{9}{8}\equiv \dfrac{145\cdot 9}{145\cdot 8}\equiv\dfrac{142}{-3}\equiv\dfrac{142\!+\!1163}{-3}\equiv -435\$$ by Gauss's algorithm

By the fractional extended Euclidean algorithm, and associated equational form

\qquad\quad \begin{align} \bmod 1163\!:\ \ \dfrac{0}{1163}\overset{\large\frown}\equiv\color{#c00}{\dfrac{-9}8}\!&\,\overset{\large\frown}\equiv\color{#0a0}{\dfrac{142}3}\overset{\large\frown}\equiv\color{#90f}{\dfrac{435}1}\\[.7em] \text{said equationally}\ \ \ \ [\![1]\!]\ \ \ \ 1163\, x&\,\equiv\ \ \ 0\ \\ [\![2]\!] \ \ \ \ \ \ \ \ \ \ \color{#c00}{8\,x}&\ \color{#c00}{ \equiv -9}\!\!\!\\ [\![1]\!]-145\,[\![2]\!] \rightarrow [\![3]\!]\ \ \ \ \ \ \ \ \ \ \color{#0a0}{3\,x} &\ \color{#0a0}{\equiv\ \ 142}\ \\ [\![2]\!]\ \ -\ \ 3\,[\![3]\!] \rightarrow [\![4]\!]\ \ \ \ \ \ \ \color{#90f}{{-1}\,x}&\ \color{#90f}{ \equiv -435} \end{align}

We can also use Newton's method (Hensel lifting) to lift inverses to higher powers, e.g. see here

For more worked examples, see here for $$5$$ ways to compute $$\,33/9\pmod{\!43}$$.

See here for general theory and algorithms to solve a linear congruence $$\,ax\equiv b\pmod{\! n}$$

Beware $$\$$ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

• Did you mean $x\equiv\color{red}-\dfrac98\equiv435$? Commented Nov 13, 2019 at 22:39
• @J.W.Tanner Updated sign to get OP"s problem. Commented Nov 13, 2019 at 22:41
• @BillDubuque very difficult way ?? How or where I can learn it ?? Commented Nov 13, 2019 at 22:53
• @EllenEllen Which way? Commented Nov 13, 2019 at 22:55
• I see you always use $\equiv \frac{a}{b}$ I never see it ?? Commented Nov 13, 2019 at 22:56

A different method:

Let, $$\frac{8n+9}{1163}=m \in\mathbb{Z^{+}}$$

\begin{align}n=\frac{1163m-9}{8} \in\mathbb{Z^{+}} \Rightarrow\frac{(145\times8+3)m-8-1}{8} \in\mathbb{Z^{+}} \Rightarrow \frac{3m-1}{8} \in\mathbb{Z^{+}} \Rightarrow \frac{8k+1}{3} \in\mathbb{Z^{+}} \Rightarrow \frac{9k+1-k}{3} \in\mathbb{Z^{+}} \Rightarrow \frac{k-1}{3} \in\mathbb{Z^{+}} \Rightarrow k=3z+1 \end {align}

$$m=\frac {8(3z+1)+1}{3}=8z+3$$ where,

$$\frac{3m-1}{8}=k \in\mathbb{Z^{+}}$$ $$\frac{k-1}{3}=z \in\mathbb{N_0}$$

Finally, we get

$$n=\frac{1163m-9}{8}=\frac{1163(8z+3)-9}{8}=1163z+435$$ where $$z \in\mathbb{N_0}$$

• Can you explain this ?? How $\frac{3m-1}{8} \in\mathbb{Z^{+}} \Rightarrow \frac{8n+1}{3}$ Commented Nov 13, 2019 at 22:36
• @EllenEllen I edited the answer. Commented Nov 13, 2019 at 22:43
• I see but I ask how you move from $\frac{3m-1}{8}$ to $\frac{8n+1}{3}$ any substation ?? Commented Nov 13, 2019 at 22:51
• @EllenEllen I fixed the substitutions. Commented Nov 13, 2019 at 23:06
• @Elvin It is fully explained there. If you have any questions please feel welcome to post them in comments. Kudos for discovering it on your own! Commented Nov 13, 2019 at 23:41

Here's an idea:

$$8n\equiv1154\equiv2317\equiv\color{red}{3480}\bmod1163$$.

Can you solve it now?

• Thanks sir @J.W.Tanner Commented Nov 13, 2019 at 22:27

If you are a one trick pony you can get the answer
using the (not always useful) shortcut found here:

$$\; 8n \equiv -9\pmod{1163} \; \text{ iff }$$
$$\; 8n \equiv 1154\pmod{1163} \; \text{ iff }$$
$$\; 4n \equiv 577\pmod{1163}$$

And since $$4 \mid 1164$$, the solution is

$$\quad x = \Large(\frac{1164}{4}) \normalsize (577) = (291)(577) = 167907 \equiv 435 \pmod{1163}$$

Of course a better trick is the one given by Laassila souhayl ($$+1$$).