Help with finding solutions to $x^3\equiv 1 \pmod{61}$ etc.

Question

"How many incongruent solutions does $x^3 \equiv 1$ have modulo 59? What about for mod 61? Now consider, $x^3 \equiv 8 \mod 59$ and $\mod61$? How about the congruences $y^5 \equiv 1$ and $y^5 \equiv 32$ mod 59 and 61? Explain your reasoning."

First of all, I'm not 100% sure what an incongruent solution is, but I'm assuming it just means the solutions you get are unique up to congruence mod 59 or 61 depending on which case you're looking at.

Looking at $x^3 \equiv 1$ (mod 61) I think this should automatically have exactly three solutions from something we proved in class since $3\mid p-1$ which is $60$ in this case. But on the others, I'm not sure where to begin or how to work this out. Any help with how to set things up would be greatly appreciated.

Answer 1

Hints:

• mod $59$, $x \mapsto x^k$ is injective for $\gcd(k,58)=1$

• $61$ has a primitive root

Answer 2

I like to think in terms of factoring. This is a nice approach when you can factor the polynomials. To start, I'll explain the case you know already $$x^3 \equiv 1 \pmod {61}$$ gives us $$ x^3 -1 \equiv 0 \pmod {61} $$ which, factoring, gives $$ (x-1)(x^2+x+1) \pmod {61} $$ which by Euclid's Lemma gives either $x \equiv 1 \pmod {61}$ or $x^2 + x + 1 \equiv 0 \pmod {61}$. The first case gives us the trivial solution, and indeed, the second has two solutions. Since $\gcd(4, 61)=1$, we have the $61 \mid n$ if and only if $61 \mid 4n$. Thus, the second equation is equivalent to $$ 4x^2 + 4x+ 4 \equiv 0 \pmod {61}$$ which, completing the square, gives $$ (2x+1)^2 + 3 \equiv 0 \pmod {61}$$ or, in turn $$(2x+1)^2 \equiv 58 \pmod {61} $$ Now, this has 2 solutions since 58 is a quadratic residue modulo 61. So, you get a full 3 solutions. But, if you do the same process $\pmod {59}$ all the intermediate steps are actually the same, so you get to $(2x+1)^2 \equiv 56 \pmod {59}$. 56 is a quadratic nonresidue modulo 59, so you only get the trivial solution.

Answer 3

Since $\mathbb{Z}/p\mathbb{Z}^*$ is a cyclic group, for any prime $p\equiv 2\pmod{3}$ the map $x\mapsto x^3$ is surjective.
If $p\equiv 1\pmod{3}$ the map $x\mapsto x^3$ is $3$-to-$1$, so $x^3\equiv 1$ has three solutions $\!\!\pmod{61}$ and just the trivial solution $\!\!\pmod{59}$. Since $59\not\equiv 1\pmod{5}$, the map $y\mapsto y^5$ is surjective $\!\!\pmod{59}$ and $y^5\equiv 1$ only has the trivial solution $\!\!\pmod{59}$. Since $61\equiv 1\pmod{5}$, the map $y\mapsto y^5$ is $5$-to-$1$ over $\mathbb{Z}/61\mathbb{Z}^*$ and $y^5\equiv 1\pmod{61}$ has five solutions.