# 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

• Hint: $$\frac{1163k-9}{8} \in\mathbb{Z^{+}} \Rightarrow\frac{(145\times8+3)k-8-1}{8} \in\mathbb{Z^{+}} \Rightarrow \cdots$$ – lone student Nov 13 '19 at 22:13
• or multiply by $8^{1161} \equiv 727\pmod {1163}$ – zwim Nov 13 '19 at 22:14
• Related to OP's earlier question. – Bill Dubuque Jan 7 '20 at 21:16

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}$ – Ellen Ellen Nov 13 '19 at 22:36
• @EllenEllen I edited the answer. – lone student Nov 13 '19 at 22:43
• I see but I ask how you move from $\frac{3m-1}{8}$ to $\frac{8n+1}{3}$ any substation ?? – Ellen Ellen Nov 13 '19 at 22:51
• @EllenEllen I fixed the substitutions. – lone student Nov 13 '19 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! – Bill Dubuque Nov 13 '19 at 23:41

$$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 ? – Ellen Ellen Nov 13 '19 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 Nov 13 '19 at 22:23
• Not always just in this case because 1163 is odd so you can divide by 2 as much as you want. – Laassila souhayl Nov 13 '19 at 22:25
• OK @lessili thanks again!😍 – Ellen Ellen Nov 13 '19 at 22:28
• @Ellen I explain the idea behind this method in my answer. – Bill Dubuque Nov 13 '19 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\$$ (see Inverse Reciprocity below)

$$\!\!\bmod 1163\!:\,\ \dfrac{1}{4}\equiv\dfrac{1164}4\equiv 291\overset{\large\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$$

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

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

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 test if this yields an exact quotient).

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{\!33}$$.

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$? – J. W. Tanner Nov 13 '19 at 22:39
• @J.W.Tanner Updated sign to get OP"s problem. – Bill Dubuque Nov 13 '19 at 22:41
• @BillDubuque very difficult way ?? How or where I can learn it ?? – Ellen Ellen Nov 13 '19 at 22:53
• @EllenEllen Which way? – Bill Dubuque Nov 13 '19 at 22:55
• I see you always use $\equiv \frac{a}{b}$ I never see it ?? – Ellen Ellen Nov 13 '19 at 22:56

Here's an idea:

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

Can you solve it now?

• Thanks sir @J.W.Tanner – Ellen Ellen Nov 13 '19 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).