[proofplan] Use the given primitive integral zero as the congruence solution for every modulus. Exact equality $q(a)=0$ in $\mathbb{Z}$ immediately implies congruence modulo $p^k$. The only point to check is primitivity modulo $p^k$: since the coordinates of $a$ have greatest common divisor $1$, no prime $p$ can divide all of them. [/proofplan] [step:Fix a prime power modulus and use the integral solution as a candidate] Let $p$ be a prime number and let $k \in \mathbb{N}$. By hypothesis, there is a vector $a = (a_1,\dots,a_n) \in \mathbb{Z}^n$ satisfying $\gcd(a_1,\dots,a_n)=1$ and $q(a)=0$. Define the candidate congruence solution $b = (b_1,\dots,b_n) \in \mathbb{Z}^n$ by \begin{align*} b_i := a_i \qquad \text{for each } i \in \{1,\dots,n\}. \end{align*} Then $b=a$, so \begin{align*} q(b)=q(a)=0. \end{align*} Since $0$ is divisible by $p^k$, this gives \begin{align*} q(b) \equiv 0 \pmod{p^k}. \end{align*} [/step] [step:Verify that the reduction is primitive modulo $p^k$] It remains to prove that not all coordinates of $b$ are divisible by $p$. Suppose, for contradiction, that $p \mid b_i$ for every $i \in \{1,\dots,n\}$. Since $b_i=a_i$ for every $i$, this means $p \mid a_i$ for every $i \in \{1,\dots,n\}$. Hence $p$ is a common divisor of $a_1,\dots,a_n$, so \begin{align*} p \mid \gcd(a_1,\dots,a_n). \end{align*} This contradicts $\gcd(a_1,\dots,a_n)=1$. Therefore at least one coordinate $b_i$ is not divisible by $p$, equivalently \begin{align*} \gcd(b_1,\dots,b_n,p)=1. \end{align*} [/step] [step:Conclude the existence of primitive solutions for every prime power modulus] For the arbitrary prime number $p$ and arbitrary $k \in \mathbb{N}$ fixed above, the vector $b=a$ satisfies both \begin{align*} q(b) \equiv 0 \pmod{p^k} \end{align*} and \begin{align*} \gcd(b_1,\dots,b_n,p)=1. \end{align*} Since $p$ and $k$ were arbitrary, the congruence $q(x)\equiv 0 \pmod{p^k}$ has a primitive solution for every prime $p$ and every $k \in \mathbb{N}$. [/step]