Let $a$ be an integer such that $\gcd(a,19 \cdot 25 \cdot 29) = 1$. Prove that the congruence $$x^{70} \equiv a \mod(19 \cdot 25 \cdot 29)$$ has either no solution or $280$ solutions in $\mathbb{Z}_{19 \cdot 25 \cdot 29}$.
The things I have thought so far:
- Since the numbers $19,25,29$ are pairwise coprime if we can break the congruence into a system of congruences and somehow apply the Chinese remainder theorem.
- Also we have $(a,19) = (a,25) = (a,29) = 1$.
- We did a result which has some similarities to this question. The result is as follows:
Prove that the linear congruence $ax \equiv c \mod(m)$ has no solution or $\gcd(m,a)$ solutions in $\mathbb{Z}_m$.
But I am unable to relate it. How is $70$ coming into the picture?
- $280 = 2^3 \times 5 \times 7 = 70 \times 4$.
Any help or hints will be useful. (The problem is a homework problem).
Best Answer
You have made a great start with your first two bullet points. However, regarding your third bullet point, consider the following lemma instead.
Lemma: For any integer $n$ which has a primitive root modulo $n$, along with fixed integers $m$ and $a$ with $\gcd(a,n) = 1$, then
$$x^m \equiv a \pmod{n} \tag{1}\label{eq1A}$$
has, for $x$, either no solutions or $\gcd(m,\varphi(n)) = d$ solutions in $\mathbb{Z}_{n}$.
Proof: Similar to what is asked & answered in Number of solutions of $x^e \equiv c \mod p$, have $g$ be a primitive root of $n$. Thus, there's a $0 \le e \le \varphi(n) - 1$ where $a \equiv g^{e} \pmod{n}$. Also, for every possible solution $x \in \mathbb{Z}_{n}$, there's a $0 \le f \le \varphi(n) - 1$ where $x \equiv g^{f} \pmod{n}$. Substituting these into \eqref{eq1A} gives
$$g^{mf} \equiv g^{e} \pmod{n} \iff g^{mf-e} \equiv 1 \pmod{n} \tag{2}\label{eq2A}$$
We therefore then also have
$$mf - e \equiv 0 \pmod{\varphi(n)} \iff mf \equiv e \pmod{\varphi(n)} \tag{3}\label{eq3A}$$
Since $d \mid m$ and $d \mid \varphi(n)$, we also require $d \mid e$. If this is not true, then there are no solutions to \eqref{eq1A}. Otherwise, have
$$\color{blue}{e = dk}, \; \color{red}{m = dh}, \; \color{green}{\varphi(n) = dj}, \; \gcd(\color{red}{h},\color{green}{j}) = 1 \tag{4}\label{eq4A}$$
Dividing both congruences and the modulus in \eqref{eq3A} by $d$, we then get
$$\color{red}{h}f \equiv \color{blue}{k} \pmod{\color{green}{j}} \iff f \equiv \color{blue}{k}\color{red}{h^{-1}} \pmod{\color{green}{j}} \tag{5}\label{eq5A}$$
Setting $s = (\color{blue}{k}\color{red}{h^{-1}} \bmod{\color{green}{j}})$, i.e., $0 \le s \le \color{green}{j} - 1$, we get that the solutions for $f$ in \eqref{eq5A}, keeping within the $0 \le f \le \varphi(n) - 1$ bounds and using that $\color{green}{\varphi(n) = dj}$ from \eqref{eq4A}, are
$$f = t\color{green}{j} + s, \; 0 \le t \le d - 1 \tag{6}\label{eq6A}$$
Thus, there are $d$ solutions for $x \equiv g^{f} \pmod{n}$ in $\mathbb{Z}_{n}$ in this case.
Your particular congruence equation is
$$x^{70} \equiv a \pmod{19 \cdot 25 \cdot 29} \tag{7}\label{eq7A}$$
If there are no solutions modulo $19$, $25$ and/or $29$, then there are no solutions overall. Otherwise, using the lemma, there are $\gcd(70,\varphi(19)) = \gcd(70,18)=2$ solutions modulo $19$, $\gcd(70,\varphi(25)) = \gcd(70,20)=10$ solutions modulo $25$, and $\gcd(70,\varphi(29)) = \gcd(70,28)=14$ solutions modulo $29$. Each of the $2(10)(14) = 280$ combinations of these solutions of $x^{70}$ has, by the Chinese remainder theorem, a unique solution modulo $19(25)(29)$. Since each solution is distinct from the others, this shows there are $280$ solutions to \eqref{eq7A} in $\mathbb{Z}_{19 \cdot 25 \cdot 29}$.