# Modulo of power sum

$$\left(\sum_{k=1}^{2011}k^n\right)\equiv0\mod n$$

Find the all possible value(s) of $n$

I have no idea to start the question

• If $n$ is a prime, then $k^n\equiv k \pmod n$ so this will only be true if and only if $n$ divides $$\sum_{k=1}^{2011} k = \frac{2011\cdot 2012}{2}=2\cdot 503 \cdot 2011$$ So the only prime solutions are $n=2,503,2011$ – Thomas Andrews Jan 22 '13 at 15:42
• How about $n$ isn't prime ???Thanks for your help!! – cwk709394 Jan 22 '13 at 16:09
• If I had a full solution, I wouldn't have put it in comments, @cwk709394 – Thomas Andrews Jan 22 '13 at 16:10
• I don't know if it's useful or not but 2,6,55,206,274,347,450 are the first few values. – Ishan Banerjee Jan 22 '13 at 17:00
• Hmm, I get a different initial set $2,6,18,222,298,503,654,894, 1006, 2011$ @IshanBanerjee – Thomas Andrews Jan 22 '13 at 17:16

(Brute force computation and some progress too long for comment.)

Brute force shows these as some of the starting solutions:

$1, 2, 6, 18, 222, 298, 503, 654, 894, \\1006, 2011, 2682, 3018, 4022, 8214, 9054, \\12066,24198, 31186, 33078, 36198, 44402$

At first, the values have only prime factors: $2,3,37, 149, 503, 2011.$ But $24198$and $31186$ have prime factors $109$ and $31$, respectively, which are new.

However, if we let $n=2011p$ where $p$ is prime, $p\neq 2011$, then, $\pmod {2011}$, the transformation $k\to k^p$ onto the $\frac{2010}{\gcd(2010,p)}$ roots of unity in $\mathbb Z_{2011}$, so they sum to $0$ in that field.

Now, we also have:

$$\sum_{k=1}^{2011} k^{2011p} \equiv \sum_{k=1}^{2011} k^{2011} \pmod p$$

So you need $p$ to be a factor of $\sum k^{2011}$ to be done. That can be lots of primes, potentially some big ones. I'm not even sure how to calculate the prime factorization of this sum.

That would seem to indicate some likely $n$ which are multiples of $2011$, depending on that factorization. In particular, the only small prime factors I've found for $\sum k^{2011}$ are $2, 479, 503, \text{ and } 2011.$ I've tried all primes up to $100000$.

Just trying $n$ as a multiple of $2011$ gives values for $n$: $$2011,2\times 2011,6\times 2011,18\times 2011, 222\times 2011, \\298\times2011, 479\times 2011, 503\times 2011, 894\times 2011, \\ 1006\times 2011, 1146\times 2011,2011\times 2011, 2682\times 2011\\ 3018\times 2011, 4022\times 2011, 8214\times 2011, 9054\times 2011$$

It's not clear how much larger it will go. Note new prime factors $497$ (as predicted above) and $191$ (a factor of $1146$.)

We can write: $$\sum_{k=1}^{2011} k^{2011} = 2^2\cdot 479 \cdot 503^2 \cdot 2011^2 K$$

where $K$ is a monster number which, in base $10$, has over 6600 digits and no prime factor smaller than $100000$. When $p$ is a prime factor of $K$, $n=2011p$ is a solution to your congruence.

Another large value for $n$ is $n=503*5701$. I think, by a similar argument to what is above, if $p$ is a prime factor of $\sum_{k=1}^{2011} k^{503}$, then $n=503p$ is a solution. This sum is $2^2\cdot 503^2 \cdot 2011^2 \cdot 5701 L$ where $L$ has 1646 digits and no prime factor smaller than a million.

Some specific results.

• $n$ cannot be divisible by $5$ or $67$ (factors of $2010$)
• If $n=3b$ then $b$ is even
• $n$ cannot be divisible by $4,7, 11, 61$.
• If $n$ is prime, then $n=2,503,2011$
• If $n=2p$ with $p$ prime, then $p=3, 149, 503, 2011$
• I think I can prove that $n=2011^j$ is a solution for all $j\geq 0$.

Here is the largest solution I've found: $n=10438214802 = 6\cdot 1739702467$, where $1739702467$ is the largest prime factor of $\sum_{k=1}^{2011} k^6$.

(I know that there are larger solutions, I just don't have specific value.)

• WOO...You are awesome – cwk709394 Jan 23 '13 at 15:50
• Suitable values for $n=503k$ has $$k=1, 2,6,18,62,222,298,503,894,1006,2011,2682,3018,3394,4022,5701,8214,\\9054, 12066,...$$ – Thomas Andrews Jan 23 '13 at 16:07
• Note, I am using the "exponentiation by square" algorithm to do these computations relatively efficiently. Computing $k^n\pmod m$ can be done in $O(\log n)$ time. See: en.wikipedia.org/wiki/Exponentiation_by_squaring – Thomas Andrews Jan 23 '13 at 16:15
• More n=503k values: $$k=...,23641,30461,33078,36198,44402,...$$ – Thomas Andrews Jan 23 '13 at 17:12