Connection between number of solutions of $x^3 \equiv 1 \pmod{m}$ and norm-Euclidean Galois cubic fields

Question

I have recently come across the following problem:

"Find the minimum value of $m \in \Bbb N$ such that $x^3 \equiv 1 \pmod{m}$ has at least $n$ solutions. Note that values of $x$ that are congruent mod $m$ are considered the same solution."

I was unable to come up with any approach. However, using a program, I was able to compute the following results and observe a pattern:

• For $n \leq 3$, the smallest $m$ was $7$.

• For $3 <n \leq 9$, the smallest $m$ was $63 = 7 \cdot 9$.

• For $9 <n \leq 27$, the smallest $m$ was $819 = 7 \cdot 9 \cdot 13$.

• For $27 <n \leq 81$, the smallest $m$ was $15561 = 7 \cdot 9 \cdot 13 \cdot 19$.

• For $81 <n \leq 243$, the smallest $m$ was $482391 = 7 \cdot 9 \cdot 13 \cdot 19 \cdot 31$.

• For $243 <n \leq 729$, the smallest $m$ was $17848467 = 7 \cdot 9 \cdot 13 \cdot 19 \cdot 31 \cdot 37$.

• For $729 <n \leq 2187$, the smallest $m$ was $767484081 = 7 \cdot 9 \cdot 13 \cdot 19 \cdot 31 \cdot 37 \cdot 43$.

A quick search of $7, 9, 13, 19, 31, 37, 43$ on OEIS yielded the finite sequence of square roots of discriminants of norm-Euclidean Galois cubic fields. It also matches the sequence of square roots of discriminants of Galois cubic number fields possessing a norm-Euclidean ideal class.

However, I am not sure what to make of this as I have just started learning modular arithmetics. Hence, I would like to ask: How is the above modular equation connected to algebraic number theory? Why are the values of $n$ bounded by powers of three? Is there an easier method to find the required $m$ given $n$? What are the consequences of the fields being finite?

Answer 1

You don't need algebraic number theory to solve your initial question. The ever useful Chinese Remainder Theorem is more or less all you need.

If $m=\prod_ip_i^{a_i}$ is the prime factorization of $m$, then CRT says that we have an isomorphism of multiplicative groups $$ \Bbb{Z}_m^*=\bigoplus_j\Bbb{Z}_{p_i^{a_i}}^*. $$ You are looking for the number of elements of order $3$ (or $1$) in this group. The prime $p=2$ is uninteresting. For all the primes $p_i>2$ it is well known that $\Bbb{Z}_{p_i^{a_i}}^*$ is cyclic of order $\phi(p_i^{a_i})=(p_i-1)p_i^{a_i-1}.$

It follows that the number of solutions of $x^3\equiv1\pmod{p_i^{a_i}}$ is three if we either have $p_i=3, a_i>1$, or $p_i\equiv1\pmod3$.

Observe that all the prime factors of the numbers you found meet this criterion. Anyway, we further observe that

• By CRT the number of solutions of $x^3\equiv1\pmod m$ is the product of the number of solutions of the same congruence modulo the prime power factors $p_i^{a_i}$.
• So for the purposes of minimizing $m$ it is pointless for $m$ to have any prime factors other than $3^2$ and $p_i^1, p_i\equiv1\pmod3$.

All the numbers you found are products of $9$ and the smallest distinct primes $\equiv1\pmod3$. That's all there is to it.