Solve the congruence : $3n^{3}+2\equiv 0 \pmod{1163}$ where $n\in \mathbb N$

127 Views Asked by At

Problem :

I'm going today to find all natural number such that : $1163 \mid 3n^{3}+2$ Mathematical give $n \equiv 435 \mod 1163$

My little try :

first we note that $1163$ prime number

$3n^{3}\equiv -2 \pmod{1163}$

Now I don't know how I complete my work My be we can use Fermat's little theorem

2

There are 2 best solutions below

8
On

The first step is to find that $3^{-1} \equiv 388 \pmod{1163}$ (can be done with Euclid's algorithm). So $$ 3n^3 + 2 \equiv 0 \iff n^3 \equiv -2\cdot 388 \equiv 387 \pmod{1163} $$ We know that $(\mathbb Z/1163\mathbb Z)^\times$ is cyclic, because $1163$ is prime. If $(\mathbb Z/1163\mathbb Z)^\times = \langle x \rangle$, then $x^3$ also generates the group, because $3$ and $1162$ (the order of the group) are coprime. That means that $a\mapsto a^3$ is an automorphism (in particular a bijection) of $(\mathbb Z/1163\mathbb Z)^\times$. In other words, any equation $n^3 \equiv m \pmod{1163}$ has a unique solution.

Now we need to find the solution. Note that $3^{-1} \equiv 775\pmod{1162}$. Thus: $$ n^3 \equiv 387 \equiv 387^{3\cdot 775} \pmod{1163} $$ Which gives $n\equiv 387^{775} \equiv 435 \pmod{1163}$.

EDIT: How to find $3^{-1}$ (with a general approach).

Use the Euclidean algorithm on $(1163,3)$: $$ 1163 = 387 \cdot 3 + 2 \\ 3 = 1 \cdot 2 + 1 $$ Now we work backwards: $$ \begin{align} 1 &= 3 - 1\cdot 2 \\ &= 3 - 1 \cdot (1163 - 387\cdot 3) \\ &= 388\cdot 3 - 1\cdot 1163 \end{align} $$ We see that $388\cdot 3 \equiv 1\pmod{1163}$, so $3^{-1} \equiv 388 \pmod{1163}$. The same approach can be used to find $3^{-1} \equiv 775\pmod{1162}$.

4
On

Hint $\,\ $ $3^{\large 7}\! = 2^{\large 10}\! + 1163\,$ $\Rightarrow\, \bmod 1163\!:\ n^{\large 3}\equiv {-}\dfrac{2}3 \equiv \left[\dfrac{-9}8\right]^{\large 3}$ and $\ \, \dfrac{-9}8 \equiv\, \bbox[5px,border:1px solid #c00]{\!\!435}$