I was given the following problem:

Let $g(n)$ be the smallest prime that divides $n^4+1$. What is the remainder of $g(1)+g(2)+...+g(2015)$ when divided by $8$?

My attempt so far:

Instead of summing up then divide $8$, i tried to find the remainder of each individual $g(n)$ when divided by $8$, then sum them up, and reduce it with modular arithmetic. So clearly for $n$ odd, $g(n)$ leaves a remainder of $2$ when divided by $8$. But for $n$ even I have no clue how to proceed.

If you can help solving this, I will greatly appreciate it.


You're on the right track. As you noted, for odd $n$, we have that $n^4 + 1$ is even, and thus its smallest prime factor is $2$; i.e., $g(n) = 2$ for odd $n$.

On the other hand, for even $n$, we have that $n^4 + 1$ is odd, and thus its smallest prime factor is odd. Furthermore, if a prime $p$ divides $n^4 + 1$, it must be the case that $-1$ has a 4th root modulo $p$; for an odd prime $p$, this is the same as saying $1$ has a primitive 8th root. Because multiplicative groups modulo primes are cyclic (as multiplicative groups in any finite field are cyclic), this will happen if and only if $p - 1$ is divisible by $8$; thus $g(n)$ for even $n$ will be 1 modulo 8.

Combining these and the fact that in the range from 1 to 2015, there are 1008 odd and 1007 even values, our final answer is $1008 * 2 + 1007 * 1 = 7 \pmod 8$.

  • $\begingroup$ You actually don't need the full fact that multiplicative groups modulo primes are cyclic to pull this off; just Fermat's Little Theorem (that every element of the multiplicative group modulo $p$ has order dividing $p - 1$) suffices to carry this argument through (since we just need the entailment from "There exists a primitive 8th root modulo $p$" to "$p - 1$ is divisible by 8", and not the converse). Anyway, if you have any further questions, let me know and I'll try to explain more. $\endgroup$ Dec 13 '16 at 9:16
  • $\begingroup$ Need more explanation on your 2nd paragraph, I do not fully understand it. $\endgroup$ Dec 13 '16 at 11:21
  • $\begingroup$ Alright. I presume you are perfectly comfortable with the first line (that if $n$ is odd, then so must be $g(n)$). As for the rest: are you familiar with Fermat's Little Theorem? $\endgroup$ Dec 13 '16 at 12:18
  • $\begingroup$ I know the Theorem directly but I am not familiar with its other applications, sorry never really learned those. $\endgroup$ Dec 13 '16 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.