1. **Problem statement:** Given an integer $n$ which is not divisible by 4, determine which number divides the sum $$1^n + 2^n + 3^n + 4^n$$. 2. To solve this, let's analyze the expression modulo different candidates: 3, 5, 7, 9. 3. **Modulo 3:** Note that modulo 3, powers cycle: - $1^n \equiv 1$ - $2^n$ alternates between $2$ and $1$ depending on $n$ (since $2^1 = 2$, $2^2 = 4 \equiv 1$ mod 3, etc.) - $3^n \equiv 0$ - $4 \equiv 1$ mod 3, so $4^n \equiv 1^n = 1$ Sum mod 3 is $1 + 2^n + 0 + 1 = 2 + 2^n$ For $n=1$, sum mod 3 = $2 + 2 = 4 \equiv 1$ (not divisible by 3) So sum not always divisible by 3. 4. **Modulo 5:** Note powers modulo 5: - $1^n = 1$ - $2^n$ cycles every 4 powers: powers are (2,4,3,1) for $n \equiv 1,2,3,0$ mod 4 - $3^n$ cycles as (3,4,2,1) - $4^n$ cycles as (4,1,4,1) Sum $= 1 + 2^n + 3^n + 4^n$ Since $n$ not divisible by 4, $n \not\equiv 0 \, (\text{mod }4)$ Check the sum for each $n$ mod 4: - If $n \equiv 1$: sum $= 1+2+3+4=10 \equiv 0$ mod 5 - If $n \equiv 2$: sum $= 1+4+4+1=10 \equiv 0$ mod 5 - If $n \equiv 3$: sum $= 1+3+2+4=10 \equiv 0$ mod 5 Hence, sum is always divisible by 5 if $n$ not divisible by 4. 5. Checking modulo 7 or 9 is unnecessary since answer is found. **Final answer:** The sum $$1^n + 2^n + 3^n + 4^n$$ is divisible by 5 when $n$ is not divisible by 4.