1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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$.

$\endgroup$
4
  • $\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$
    – Sridhar Ramesh
    Dec 13, 2016 at 9:16
  • $\begingroup$ Need more explanation on your 2nd paragraph, I do not fully understand it. $\endgroup$
    – MathEnthusiast
    Dec 13, 2016 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$
    – Sridhar Ramesh
    Dec 13, 2016 at 12:18
  • $\begingroup$ I know the Theorem directly but I am not familiar with its other applications, sorry never really learned those. $\endgroup$
    – MathEnthusiast
    Dec 13, 2016 at 12:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .