Let $ k>1$ be an integer. Prove that there exists infinitely many natural numbers such as $ n$ such that: \[ n|1^n+2^n+\dots+k^n\]
Problem
Source: Iranian National Olympiad (3rd Round) 2008
Tags: induction, number theory proposed, number theory
30.08.2008 20:54
A lemma : If $ p$ is an odd prime and $ p|x+y$ then we have \[ p^k|x^{p^k}+y^{p^{k}} \] It is an well know result .We can prove it by induction on k . Now consider our problem . We consider two cases : Case 1 $ k\equiv 0(\mod 2)$ Call p is a prime divisor of $ k+1$ . From condition k is an even number so $ p$ is an odd prime . From lemma we have : \[ p^a|x^{p^a}+(k-x)^{p^a},\forall x=1,..,\frac{k-1}{2} \] Therefore : $ p^a|\sum_{x=1}^k x^{p^a}$ It means that $ n=p^a,a>0$ satisfy condition . Case 2 $ k\equiv 1 (\mod 2)$ Similar the case 1 we consider an odd prime of $ k+1$ then we have \[ p^a|x^{p^a}+(k-1-x)^{p^a} \] And \[ p^a|k^{p^a} \] Therefore : $ p^a|\sum_{x=1}^k x^{p^a}$ It means that $ p^a,a>0$ satisfy condition . Problem claim .
30.08.2008 23:13
the same as he said but we can use Hensel lemma: Hensel lemma:if we denote $ ||x||(p)$ the largest power of p that divide $ x$ and if p is odd prime number such that$ p|a-b$ we have $ ||a^n-b^n||(p)=||a-b||(p)+||n||(p)$ so if we put $ n=p^t$where $ p|k+1$ we reach to soloution
31.08.2008 07:40
TTsphn wrote: A lemma : If $ p$ is an odd prime and $ p|x + y$ then we have \[ p^k|x^{p^k} + y^{p^{k}} \] It is an well know result .We can prove it by induction on k . Now consider our problem . We consider two cases : Case 1 $ k\equiv 0(\mod 2)$ Call p is a prime divisor of $ k + 1$ . From condition k is an even number so $ p$ is an odd prime . From lemma we have : \[ p^a|x^{p^a} + (k - x)^{p^a},\forall x = 1,..,\frac {k - 1}{2} \] Therefore : $ p^a|\sum_{x = 1}^k x^{p^a}$ It means that $ n = p^a,a > 0$ satisfy condition . Case 2 $ k\equiv 1 (\mod 2)$ Similar the case 1 we consider an odd prime of $ k + 1$ then we have \[ p^a|x^{p^a} + (k - 1 - x)^{p^a} \] And \[ p^a|k^{p^a} \] Therefore : $ p^a|\sum_{x = 1}^k x^{p^a}$ It means that $ p^a,a > 0$ satisfy condition . Problem claim . Nice,TTsphn,But is it useful with $ n^2|1^n+2^n+..k^n$ I had a solution for it
05.09.2008 13:22
sumita wrote: the same as he said but we can use Hensel lemma: Hensel lemma:if we denote $ ||x||(p)$ the largest power of p that divide $ x$ and if p is odd prime number such that$ p|a - b$ we have $ ||a^n - b^n||(p) = ||a - b||(p) + ||n||(p)$ so if we put $ n = p^t$where $ p|k + 1$ we reach to soloution Dear Sumita , I think if $ k+1=2^{m}$ ur solution is wrong . I prove this problem with Primitive root if $ p$ is odd prime number such that $ p|1+2+\cdots+k$ then u can prove : $ n=p^{a}$ for each $ a$ is a good number .
23.07.2009 14:53
Allnames,can you post your solutions with your own problem? I'm really interested in it.
01.08.2024 14:44
My solution is very similar to TTsphn: First consider the case, where $k$ is even. Then we can clearly choose an odd prime $p$ dividing $k+1$. We will prove that: \[ p^a \mid 1^{p^a} + 2^{p^a} + \cdots + k^{p^a} \]We would like to prove that $\nu_p(1^{p^a}+\cdots+ k^{p^a}) \ge \nu_p(p^a)$. Put the numbers into pairs with sum $k+1$. From LTE we get that $\nu_p((k-x)^{p^a}+(x+1)^{p^a})=\nu_p(k+1)+a \ge a+1 > a = \nu_p(p^a)$. Meaning: \[ \nu_p(1^{p^a} + \cdots + k^{p^a}) \ge min(\nu_p(1^{p^a}+k^{p^a}), \nu_p(2^{p^a}+(k-1)^{p^a})) = \nu_p((k-x)^{p^a}+(x+1)^{p^a}) > \nu_p(p^a) \]which is the desired result. For $k$ odd, just consider an odd prime $p$ dividing $k$. Put the numbers into pairs with sum of $k$ (except $k$). From LTE we get that for each pair: \[ \nu_p((k-1-x)^{p^a} + (x+1)^{p^a}) = \nu_p(k) + a > a = \nu_p(p^a) \]For $k^{p^a}$ we get $\nu_p(k^{p^a}) = p^a \nu_p(k) \ge p^a > a = \nu_p(p^a)$. Since each of these terms has their $p$-adic valuation bigger than $p^a$, it follows that their sum also does. $\square$