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

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

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

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

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.

Here's an idea:

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

Can you solve it now?