# Chinese reminder Theorem and primitive roots

The problem I am working on is "Let $p$ be a prime such that $p\equiv 1\pmod{105}$. Show that there exist integers $n, x, y, z$ such that $p$ does not divide $n$ and $n \equiv 3x^3 \equiv 5y^5 \equiv 7z^7 \pmod p$.

I'm looking for suggestions on how to approach this. I think I want to set up a series of equations so that I can use the Chinese Remainder theory to reduce them to something I can demonstrate is solvable.

I've also been looking at primitive roots - there is a primitive root, $g$ that generates $\mathbb{Z}_p$ which will have an order $105k$ for some integer $k$, but other than writing $x, y, z$ in terms of $g$, I'm not getting anywhere with this.

My instinct is to take $n = 105$, which would let me reduce to showing 35 has a cube root, 21 has a fifth root and 15 has a seventh root, but I'm not getting anywhere with that approach.

I'd very much appreciate any suggestions.

We look for a solution of the shape $n=3^a5^b7^c$.
We want $n$ to be congruent to $3x^3$ modulo $p$. That makes $9n$ a perfect cube modulo $p$. If a number is a plain perfect cube, then it is a perfect cube modulo $p$. It follows that if we take $$a\equiv -2\pmod{3},\quad b\equiv 0\pmod{3},\quad c\equiv 0\pmod{3},$$ then $9\cdot 3^a5^b7^c$ will be a perfect cube modulo $p$.
Similarly, it is enough to make $5^4n$ a perfect fifth power. That gives the congruences $$a\equiv 0\pmod{5},\quad b\equiv -4\pmod{5},\quad c\equiv 0\pmod{5}.$$ A similar analysis for $7$ gives $$a\equiv 0\pmod{7},\quad b\equiv 0\pmod{5},\quad c\equiv -6\pmod{7}.$$
We get a system of $3$ congruences for each of $a$, $b$, and $c$. They are no trouble to solve.
Remark: The modulus $p$ played essentially no role, and the Chinese Remainder Theorem, though in principle present, is not really needed. We can find other solutions by using $k^{105}3^a5^b7^c$ with any $k$ relatively prime to $p$.
• @user26486: Thank you for spotting the mismatch of letters, and the missing $9$. – André Nicolas Jun 21 '15 at 3:16