Problem 1846

First observe that if $a_i \equiv b_i \pmod r$, $i = 1, 2, \dots, n$ then $p(a_1, a_2, \dots, a_n) \equiv p(b_1, b_2, \dots, b_n) \pmod r$. If $u$ and $v$ are coprime then given $b_1, b_2, \dots, b_n$ and $c_1, c_2, \dots, c_n$ with $0 \le b_i < u$ and $0 \le c_i < v$ by the chinese remainder theorem there exist unique integers $a_1, a_2, \dots, a_n$ with $0 \le a_i < uv$ such that $a_i \equiv b_i \pmod u$ and $a_i \equiv c_i \pmod v$, which imply $p(a_1, a_2, \dots, a_n) \equiv p(b_1, b_2, \dots, b_n) \pmod u$, $p(a_1, a_2, \dots, a_n) \equiv p(c_1, c_2, \dots, c_n) \pmod v$. Thus
$$\gcd(p(a_1, a_2, \dots, a_n), uv) = 1 \iff \begin{cases} \gcd(p(a_1, a_2, \dots, a_n), u) = 1 \\ \gcd(p(a_1, a_2, \dots, a_n), v) = 1 \end{cases}$$
and $k(uv) = k(u) \cdot k(v)$.
For $p$ prime $\gcd(p(a_1, a_2, \dots, a_n), p^s) = 1 \iff \gcd(p(a_1, a_2, \dots, a_n), p) = 1$. Divide each $a_i$ by $p$, obtaining quotient $q_i$ and remainder $r_i$. Reducing modulo $p$, we obtain $\gcd(p(a_1, a_2, \dots, a_n), p) = 1 \iff \gcd(p(r_1, r_2, \dots, r_n), p) = 1$. Given $r_i$ there are $p^s/p = p^{s-1}$ possibilities for $q_i$ such that $0 \le a_i < p^s$. Hence $k(p^s) = (p^{s-1})^n k(p) = p^{n(s-1)} k(p)$, as required.