Number of solutions of $y^2=x^3$ in $\mathbb{Z}_{57}$

Question

The title explains the question. It was one of the 25 questions of a 3 hour olympiad, so I hope it is not too hard. The olympiad is for undergraduate students, so I also hope it doesn't use any "too advanced maths". I've tried to do some elementar number theory to tackle this problem like seeing that when $x = 3k+2$, there is no solution and I've found all solutions for some values of $x$, but that's it. I've also thought about solving the equation in $\mathbb{Z}_3$ and $\mathbb{Z}_{19}$ but gave up as soon as I realized I didn't know how to easily put together two of these solutions to form a solution on $\mathbb{Z}_{57}$

Answer 1

You just multiply the numbers of solutions in $Z_3$ and $Z_{19}$. That's because of the Chinese Remainder Theorem, $Z_3 \oplus Z_{19}=Z_{57}$.

Answer 2

Solve it modulo $3$ and $19$. To get a solution mod $57$, start with a solution mod $19$ and add $19$ until it gives one of your solutions mod $3$.

For example, $(x,y)=(2,1)$ is a solution mod $3$ and $(x,y)=(18,1)$ is a solution modulo $19$. We can take $(x,y)=(18,1)$ and modify it to get $(x,y)\equiv (2,1) \bmod 3$. To do this, just add 19 to the coordinates until it works.

$$(18,1)\to (37,1)\to (56,1)$$

Now $(56,1)\equiv (18,1)\bmod 19$ because adding 19 does not change it, and $(56,1)\equiv (2,1)\bmod 3$.

For further reading, look up the Chinese remainder theorem.

Answer 3

Initially, I had thought of the Chinese Remainder Theorem as the others have pointed out, but I thought it didn't work. Why does a pair of solutions $((a, b), (c,d))$ in $\mathbb{Z}_3$ and $\mathbb{Z}_{19}$ actually produce a valid solution in $\mathbb{Z}_{57}$? So with the answers provided I've done the following solution. While solving it I found some facts that made me conjecture about the general case.

Describe an element of $\mathbb{Z}_{57}$ as an ordered pair $(a, b)$ where $a \in \mathbb{Z}_3$ and $b \in \mathbb{Z}_{19}$. Applying the Chinese remainder theorem, this ordered pair corresponds to the element $19a + 39b$. Note that if $( (a, b), (c, d))$ is a solution $(a, b)^2 = (c, d)^3$ in $\mathbb{Z}_{57}$ , we have that $a^2 = c^3$ and $b^2 = d^3$ are true relations in $\mathbb{Z}_3$ and $\mathbb{Z}_{19}$. This means that there is an injection of the solution set in $\mathbb{Z}_{57}$ to the Cartesian product of the solution sets of this equation in $\mathbb{Z}_3$ and $\mathbb{Z}_{19}$ given by $((a, b), (c, d)) \to ((a, c), (b, d))$.

Now, take a solution $a^2 = c^3$ in $\mathbb{Z}_3$ and a $b^2 = d^3$ in $\mathbb{Z}_{19}$. We will have, in $\mathbb{Z}_{57}$,

$$ (a, b)^2 = (c, d)^3 \Longleftrightarrow (19a+39b)^2 = (19c + 39d)^3 \Longleftrightarrow$$

$$ 19^2 a^2 + 2 \cdot 19 \cdot 39 ab + 39^2 b^2 = 19^3 c^3 + 3 (19c)^2 \cdot 39d + (19c) \cdot (39d) ^2 + (39d)^3 \Longleftrightarrow$$

$$19^2 a^2 + 39^2 b^2 = 19^3 c^3 + 39^3 d^3 \Longleftrightarrow 19^2 c^3 + 39^2 d^3 = 19^3 c^3 + 39^3 d^3 \Longleftrightarrow$$

$$(19^2-19^3)c^3 = (39^3 - 39^2)d^3 $$

But $19^2 - 19^3 = 0$ and $39^3 - 39^2 = 0$, so this is equivalent to $0 = 0$, so there is an injection from the Cartesian product between the set of solutions in $\mathbb {Z}_3$ and in $\mathbb{Z}_{19}$ to the set of solutions in $\mathbb{Z}_{57}$. Therefore, there is a bijection between these two sets and it is enough to count the number of solutions in $\mathbb{Z}_3$ and in $\mathbb{Z}_{19}$. It is easy to verify that in $\mathbb{Z}_3$ we have the solutions $(0, 0), (1, 1)$ and $(2, 1)$. In $\mathbb{Z}_{19}$ the quadratic residues are $\{0, 1, 4, 5, 6, 7, 9, 11, 16, 17\}$. The cubic residues are $\{0, 1, 7, 8, 11, 12, 18 \}$. The intersection of these sets is $\{ 0, 1, 7, 11\}$. Disregarding zero, each of these cubic residues happens $3$ times and the quadratics $2$ times. So the answer is $3 \cdot 2 \cdot 3 + 1 = 19$ (I wonder if this is a coincidence!). So the final answer is $19 \cdot 3 = 57$.

So with this, a few questions arised. Is the answer for $\mathbb{Z}_{p}$ equal to $p$ (prime)? Very likely. Is the answer for a distinct product of primes $p_1 \dots p_n$ equal to $p_1 \dots p_n$? Yes, provided that the answer for $\mathbb{Z}_p$ is $p$. What about the answer for $p^k$? With this, we'll get the answer for a general $n$ because this chinese remainder theorem proof can be adapted to prove that if $f$ is the number of solutons functions, we'll have $f(mn) = f(m)f(n)$ whenever $gcd(m, n) = 1$.