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

Question

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

Answer 1

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

Answer 2

Here's an idea:

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

Can you solve it now?

Answer 3

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

Answer 4

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.

Answer 5

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