1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Note that $3\,\nmid\,58$ so there are no elements of order exactly $3$ $\pmod {58}$ (though of course there is an element of order $1$). $\endgroup$ – lulu Oct 1 at 0:11
  • $\begingroup$ Does this mean that there is only one (and it's trivial) solution for the case $x^3 ≡ 1$ (mod 59)? which is just x=1 which is always the case for this. Also how can I relate this to the cases with other numbers instead of just 1? $\endgroup$ – deviant_lime Oct 1 at 0:13
  • $\begingroup$ Well, if we had $x^3\equiv y^3\equiv a\not \equiv 0 \pmod p$ then $\left( \frac xy\right)^3\equiv 1 \pmod p$. $\endgroup$ – lulu Oct 1 at 0:17
  • 1
    $\begingroup$ But, if you have never studied these things abstractly, perhaps you are meant to simply solve them computationally. Using a spreadsheet or a program, it's not difficult to simply check all the possible cases. $\endgroup$ – lulu Oct 1 at 0:18
  • $\begingroup$ We are supposed to solve them abstractly as it's a proof based course. Thank you for the help your last comment seems to have made things clearer in terms of the other numbers question. So am I correct in thinking that at the ones mod 51 will only have x is congruent to 1 as a solution and the ones mod 61 will have 3 or 5 solutions depending on the power x is taken to? $\endgroup$ – deviant_lime Oct 1 at 0:21
2
$\begingroup$

Hints:

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

  • $61$ has a primitive root

$\endgroup$
  • 1
    $\begingroup$ Hi, I'm sorry I haven't taken any algebra yet so could you explain that explicitly in terms of number theory terms? $\endgroup$ – deviant_lime Oct 1 at 0:15
  • $\begingroup$ @deviant_lime, makes more sense now? $\endgroup$ – lhf Oct 1 at 0:17
  • $\begingroup$ Yes thank you very much! $\endgroup$ – deviant_lime Oct 1 at 0:22
  • $\begingroup$ @lhf I think that may be the single greatest edit I have ever seen on MSE. The working out of the same argument on two different levels is really delicious. Just. Bravo. $\endgroup$ – Cade Reinberger Oct 1 at 0:35
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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