Question:

Step 1: Analyze $3^p$ using modular arithmetic. We expand $3^p$ by writing it as $(4-1)^p$. Using the binomial theorem, we can determine its value modulo 4. $$ 3^p = (4-1)^p = \sum_{k=0}^{p} \binom{p}{k} 4^k (-1)^{p-k} $$ When expanded, every term except the first one $\binom{p}{0}(-1)^p$ will be a multiple of 4. $$ 3^p = \binom{p}{0}(-1)^p + \binom{p}{1}4(-1)^{p-1} + \dots + \binom{p}{p}4^p $$ $$ 3^p = (-1)^p + 4p(-1)^{p-1} + \text{terms divisible by } 4^2 \text{ or higher powers of 4} $$ Thus, we can write $3^p$ in the form $4x_1 + (-1)^p$ for some integer $x_1$. $$ 3^p = 4x_1 + (-1)^p $$ Step 2: Analyze $5^q$ using modular arithmetic. We expand $5^q$ by writing it as $(4+1)^q$. Using the binomial theorem, we determine its value modulo 4. $$ 5^q = (4+1)^q = \sum_{k=0}^{q} \binom{q}{k} 4^k (1)^{q-k} $$ When expanded, every term except the first one $\binom{q}{0}(1)^q$ will be a multiple of 4. $$ 5^q = \binom{q}{0}(1)^q + \binom{q}{1}4(1)^{q-1} + \dots + \binom{q}{q}4^q $$ $$ 5^q = 1 + 4q + \text{terms divisible by } 4^2 \text{ or higher powers of 4} $$ Thus, we can write $5^q$ in the form $4x_2 + 1$ for some integer $x_2$. $$ 5^q = 4x_2 + 1 $$ Step 3: Analyze $7^r$ using modular arithmetic. We expand $7^r$ by writing it as $(8-1)^r$. Using the binomial theorem, we determine its value modulo 8. $$ 7^r = (8-1)^r = \sum_{k=0}^{r} \binom{r}{k} 8^k (-1)^{r-k} $$ When expanded, every term except the first one $\binom{r}{0}(-1)^r$ will be a multiple of 8. $$ 7^r = \binom{r}{0}(-1)^r + \binom{r}{1}8(-1)^{r-1} + \dots + \binom{r}{r}8^r $$ $$ 7^r = (-1)^r + 8r(-1)^{r-1} + \text{terms divisible by } 8^2 \text{ or higher powers of 8} $$ Thus, we can write $7^r$ in the form $8x_3 + (-1)^r$ for some integer $x_3$. $$ 7^r = 8x_3 + (-1)^r $$ Step 4: Determine the parity implications from the $5^q$ expansion. From Step 2, we found that $5^q \equiv 1 \pmod{4}$ for all values of $q$. This means $5^q$ is always one more than a multiple of 4, i.e., of the form $4k+1$. The original solution states that this implies it's always even. From the second equation, $5^q \equiv 1 \pmod{4}$ for all $q$, so it's always even. Step 5: Establish the parity relationship between $p$ and $r$. Based on the expressions for $3^p$ and $7^r$ (from Step 1 and Step 3), the original solution concludes a relationship between the parities of $p$ and $r$. For the first and third expressions, both $p$ and $r$ must be odd or both even. Step 6: Determine the parity of $p+r$ and $p+q+r$. From Step 5, since $p$ and $r$ must have the same parity (both odd or both even), their sum $p+r$ will always be even (odd + odd = even; even + even = even). The parity of $q$ is not constrained. Therefore, the sum $p+q+r = (p+r) + q$ can be either even (if $q$ is even) or odd (if $q$ is odd). Therefore $p+r$ is always even, while $p+q+r$ can be either odd or even.