Find all solutions to the congruence $x^3\equiv 1 {\pmod{77}}$

Question

Find all solutions to the congruence $x^3\equiv 1 \pmod{77}$

I was able to do this for $x^2 \equiv 1\pmod{77}$ since $x$ would either be $1$ or $-1$, in each of $\bmod 7$ and $\bmod 11$. I don't know what $x$ would be in this case.

I can do the Chinese remainder theorem to find the final answers.

Answer 1

For prime $p, \mathbb Z_p^\times$ is cyclic a group of order $p-1$

Suppose, $x^a \equiv 1 \mod p$

Then $\{x, x^2, \cdots , x^{a-1}\}$ forms a sub-group and the order of the subgroup must divide $(p-1)$

Since $3$ does not divide $10$

The only solution to: $x^3 \equiv 1\pmod {11}$ is the trivial $x \equiv 1\pmod {11}$

But $3$ does divide $6$

$x^3 \equiv 1 \pmod 7$ has $3$ solutions (incuding $x = 1$)

If you find a non-trival solution then $x^2$ is also a solution.

Answer 2

Presumably you know that Fermat's little theorem (FLT) says that for prime modulus $p$ and $a$ coprime to $p$ we have $a^{p-1}\equiv 1 \bmod p$.

This also means that if we have $a^k \equiv 1 \bmod p$, and $k$ is the smallest positive integer for which this is true ($k$ is the order of $a \bmod p$), then $k$ divides $p{-}1$ - since otherwise FLT would not hold.

This means that we cannot have any such elements for $p=11$ and $k=3$, since $3 \nmid 10$. So $x^3\equiv 1 \bmod 11$ has only one solution, $x\equiv 1 \bmod 11$, since only $1$ divides both $3$ and $10$.

By constrast $3\mid (7-1) $ so there should be three solutions (including $1$), and $7$ is small enough to search case-by-case even if $7+1=8=2^3$ doesn't occur to you. The other cube root is $2^2 = 4$, which is apparent without further multiplying-out since $4^3=2^6\equiv 1^2\equiv 1 \bmod 7$.

Answer 3

As often in modular arithmetic, the most natural approach is via the Chinese Remainder theorem, which gives you an isomorphism of rings $\mathbf Z/77 \cong \mathbf Z/7 \times \mathbf Z/11 $, which in turn induces an isomorphism of multiplicative groups $(\mathbf Z/77)^* \cong (\mathbf Z/7)^* \times (\mathbf Z/11)^* $ between the corresponding groups of invertible elements. For a given prime $p$, the group $(\mathbf Z/p)^*$ is classically known to be cyclic of order $(p-1)$ (this is a precise version of FLT) and consequently, for a divisor $q$ of $(p-1)$, the elements of order $q$ of $(\mathbf Z/p)^*$ constitute the unique subgroup of order $q$, which is generated by $[y]^\frac {p-1}q$ if $[y]$ is a generator of $(\mathbf Z/p)^*$. Here $q=3$ divides $6$ and does not divide $10$, so $x^3\equiv 1$ mod $77$ iff $x\equiv 1$ mod $11$ and $x\equiv z^2$ mod $7$, $[z]$ being a generator of $(\mathbf Z/7)^*$. You can guess and check that $[x]=[2]$ will do, but as a general procedure, you could again use the CRT, which gives an isomorphism of multiplicative groups groups $C_6 \cong C_2 \times C_3 $, hence ${C_6}^2 \cong C_3 $ because $2$ and $3$ are coprime.

Answer 4

As a solution to $x^2 \equiv 1 \mod 77$ you should have gotten

$x \equiv \pm 1 \mod 7$ and $x \equiv \pm 1 \mod 11$. As this is FOUR systems of equations each system of equations should have yielded one unique solution.

System 1: $x \equiv 1\mod 7$ and $x \equiv 1 \mod 11$ yields $x \equiv 1 \mod 77$.

System 2: $x \equiv 1 \mod 7$ and $x \equiv -1 \mod 11$ yields $x \equiv 43 \mod 77$. And $43^2 = 24*77 + 1$.

System 3: $x \equiv -1 \mod 7$ and $x \equiv 1 \mod 11$ yields $x \equiv 34 \mod 77$. And $34^2 = 15*77 + 1$.

System 4: $x \equiv -1 \mod 7$ and $x \equiv - 1 \mod 11$ yields $x \equiv 76\equiv -1 \mod 77$.

====

For $x^3 = 1 \mod 77$.

To solve $x^3 \equiv 1 \mod 7$. Note that if $x\not \equiv 0$ then $x^6 \equiv 1 \mod 7$ so $(x^2)^3 \equiv 1 \mod 7$ and so if $x \equiv (\pm 1)^2,(\pm 2)^2, (\pm 3)^2 \equiv 1, 4, 2 \mod 7$ then $x^3 \equiv 1 \mod 7$.

To solve $x^3 \equiv 1 \mod 11$, note that $\phi(11) = 10$. $\gcd(3,10) = 1$. For $x^k \equiv 1 \mod 11$ then $x\equiv y^j$ for some $j$ and $10|j*k$. That can only happen if $k = 10$ or $k < 10$ and $j=10$. So $x \equiv 1 \mod 11$ is the only solution to $x^3 \equiv 1 \mod 11$.

So we have $3$ systems of equations.

$x \equiv 1 \mod 7$ and $x\equiv 1 \mod 11$ yields $x \equiv 1 \mod 77$.

$x \equiv 2 \mod 7$ and $x \equiv 1 \mod 11$ yields $x\equiv 23 \mod 77$. And $23^3 = 12167 = 1 + 158*77$.

$x \equiv 4 \mod 7$ and $x \equiv 1 \mod 11$ yeilds $x \equiv 67 \mod 77$. And $67^3 \equiv (-10)^3 \equiv -1000 + 770 \equiv -230 + 385 \equiv 155 - 154 \equiv 1 \mod 77$.