3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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$ $\endgroup$ – Thomas Andrews Jan 22 '13 at 15:42
  • $\begingroup$ How about $n$ isn't prime ???Thanks for your help!! $\endgroup$ – cwk709394 Jan 22 '13 at 16:09
  • $\begingroup$ If I had a full solution, I wouldn't have put it in comments, @cwk709394 $\endgroup$ – Thomas Andrews Jan 22 '13 at 16:10
  • 2
    $\begingroup$ I don't know if it's useful or not but 2,6,55,206,274,347,450 are the first few values. $\endgroup$ – Ishan Banerjee Jan 22 '13 at 17:00
  • $\begingroup$ Hmm, I get a different initial set $2,6,18,222,298,503,654,894, 1006, 2011$ @IshanBanerjee $\endgroup$ – Thomas Andrews Jan 22 '13 at 17:16
2
$\begingroup$

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

Additional note:

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

$\endgroup$
  • $\begingroup$ WOO...You are awesome $\endgroup$ – cwk709394 Jan 23 '13 at 15:50
  • $\begingroup$ 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,...$$ $\endgroup$ – Thomas Andrews Jan 23 '13 at 16:07
  • $\begingroup$ 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 $\endgroup$ – Thomas Andrews Jan 23 '13 at 16:15
  • $\begingroup$ More n=503k values: $$k=...,23641,30461,33078,36198,44402,...$$ $\endgroup$ – Thomas Andrews Jan 23 '13 at 17:12

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.