1. For a positive integer $n$, let $\varphi(n)$ denote the number of positive integers less than and relatively prime to $n$. Let $S_{k}=\sum_{n} \frac{\varphi(n)}{n}$, where $n$ runs through all positive divisors of $42^{k}$. Find the largest positive integer $k<1000$ such that $S_{k}$ is an integer.
1. For a positive integer $n$, let $\varphi(n)$ denote the number of positive integers less than and relatively prime to $n$. Let $S_{k}=\sum_{n} \frac{\varphi(n)}{n}$, where $n$ runs through all positive divisors of $42^{k}$. Find the largest positive integer $k2$. Note that the problem defines $\varphi(1)=0$.
For any $k \in \mathbb{N}$, the number $42^{k}$ has $(k+1)^{3}$ factors, each of which takes the form $2^{a} 3^{b} 7^{c}$ where $a, b, c \in\{0,1,2, \ldots, k\}$. Since $\varphi(n) / n$ depends only on the prime factors of $n$, we partition this set of factors into 8 forms with the same value for $\varphi(n) / n$.
\begin{tabular}{|c|c|c|c|c|}
\hline & form of $n$ & \begin{tabular}{l} 
number of \\
such $n$ s
\end{tabular} & \begin{tabular}{l}
$\frac{\varphi(n)}{n}$
\end{tabular} & \begin{tabular}{l} 
contribution \\
to the sum
\end{tabular} \\
\hline 1 & 1 & 1 & 0 & 0 \\
\hline 2 & $2^{a} ; a=1,2, \ldots, k$ & $k$ & \begin{tabular}{l}
$\left(1-\frac{1}{2}\right)=\frac{1}{2}$
\end{tabular} & \begin{tabular}{l}
$\frac{k}{2}$
\end{tabular} \\
\hline 3 & $3^{b} ; b=1,2, \ldots, k$ & $k$ & $\left(1-\frac{1}{3}\right)=\frac{2}{3}$ & \begin{tabular}{l}
$\frac{2 k}{3}$
\end{tabular} \\
\hline 4 & $7^{c} ; c=1,2, \ldots, k$ & $k$ & \begin{tabular}{l}
$\left(1-\frac{1}{7}\right)=\frac{6}{7}$
\end{tabular} & \begin{tabular}{l}
$\frac{6 k}{7}$
\end{tabular} \\
\hline 5 & $2^{a} 3^{b} ; a, b=1,2, \ldots, k$ & $k^{2}$ & \begin{tabular}{l}
$\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=\frac{1}{3}$
\end{tabular} & \begin{tabular}{l}
$\frac{k^{2}}{3}$
\end{tabular} \\
\hline 6 & $2^{a} 7^{c} ; a, c=1,2, \ldots, k$ & $k^{2}$ & $\left(1-\frac{1}{2}\right)\left(1-\frac{1}{7}\right)=\frac{3}{7}$ & \begin{tabular}{l}
$\frac{3 k^{2}}{7}$
\end{tabular} \\
\hline 7 & $3^{b} 7^{c} ; b, c=1,2, \ldots, k$ & $k^{2}$ & \begin{tabular}{l}
$\left(1-\frac{1}{3}\right)\left(1-\frac{1}{7}\right)=\frac{4}{7}$
\end{tabular} & \begin{tabular}{l}
$\frac{4 k^{2}}{7}$
\end{tabular} \\
\hline 8 & $2^{a} 3^{b} 7^{c}, a, b, c=1,2, \ldots, k$ & $k^{3}$ & \begin{tabular}{l}
$\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{7}\right)=\frac{2}{7}$
\end{tabular} & \begin{tabular}{l}
$\frac{2 k^{3}}{7}$
\end{tabular} \\
\hline
\end{tabular}

Therefore, $S_{k}=\frac{k}{2}+\frac{2 k}{3}+\frac{6 k}{7}+\frac{k^{2}}{3}+\frac{3 k^{2}}{7}+\frac{4 k^{2}}{7}+\frac{2 k^{3}}{7}=\frac{a(k)}{42}$, where $a(k)=85 k+56 k^{2}+12 k^{3}$. Hence, the problem wants us to find the largest $k<10^{3}$ so that $a(k) \equiv 0(\bmod 42)$, or equivalently, $a(k) \equiv 0(\bmod 2), a(k) \equiv 0(\bmod 3)$, and $a(k) \equiv 0(\bmod 7)$. Observe that
- $a(k) \equiv k(\bmod 2)$, which is 0 iff $k$ is even.
- $a(k) \equiv k+2 k^{2}(\bmod 3)$, which is 0 iff $k \equiv 0$ or $1(\bmod 3)$
- $a(k) \equiv k+5 k^{3}(\bmod 7)$, which is 0 iff $k \equiv 0,2$, or $5(\bmod 7)$.

The numbers 999 and 997 are not even. $998 \equiv 2(\bmod 3) .996$ is even, $\equiv 0(\bmod 3)$, and $\equiv 2(\bmod 7)$. Therefore, the answer is 996