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

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

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

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.

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

• You should post your last paragraph as a separate question. I have answers to your questions. Commented Aug 28, 2023 at 11:43