5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do it mod $7$ and mod $11$ (both easy), and combine the results using the Chinese remainder theorem. $\endgroup$ – Robert Israel Apr 3 '18 at 0:14
  • $\begingroup$ @Brooke When you did $x^2 \equiv 1 \pmod {77}$, are you sure there are no other solutions other than $-1$ or $1$? $\endgroup$ – Toby Mak Apr 3 '18 at 0:17
  • $\begingroup$ there are 4 solutions which you get mod 7 and mod 11. I dont know how to do x^3 in mod 7 and 11 $\endgroup$ – Brooke Apr 3 '18 at 0:22
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.