Let $n$ be a positive integer such that the number \[\frac{1^k + 2^k + \dots + n^k}{n}\]is an integer for any $k \in \{1, 2, \dots, 99\}$. Prove that $n$ has no divisors between 2 and 100, inclusive.
Problem
Source: USA TST for EGMO 2019, Problem 3 (adapted from IMO TST Problem 2)
Tags: number theory
10.12.2018 21:37
10.12.2018 21:42
trumpeter wrote: Suppose $p<100$ divides $n$. Let $e=\nu_p\left(n\right)$, $d=\frac{n}{p^e}$. Then $p^e$ divides \[\displaystyle\sum_{i=1}^ni^{\varphi\left(p^e\right)}\equiv d\displaystyle\sum_{i=1}^{p^e}i^{\varphi\left(p^e\right)}\pmod{p^e}.\]But $i^{\varphi\left(p^e\right)}$ evaluates to $1$ when $p\nmid i$ and $0$ otherwise (clearly $\varphi\left(p^e\right)\geq e$), so this is $0\equiv d\varphi\left(p^e\right)\pmod{p^e}$. But then $p\mid d$, contradiction. It is not necessarily true that $\varphi(p^e)\in\{1, 2, \dotsc, 99\}$.
10.12.2018 22:52
Suppose that a prime $p<100$ divides $n$. It is not hard to prove that $B_{p-1}$ is the first Bernoulli number whose denominator is divisible by $p$ (it follows directly from the classical baby-version of the problem which is solvable with primitve roots). Thus by Faulhaber $n$ can't divide $p-1$th power sum.
10.12.2018 23:07
@Above Unless $p^2|n$...?
10.12.2018 23:16
It's sufficient to show that $v_p(n)>v_p(\sum_{k=1}^n k^{p-1})$ when $p \mid n$.
10.12.2018 23:17
Hamel wrote: @Above Unless $p^2|n$...? If $u=v_p(n)$ then note that $nB_{p-1}$ is not $0\pmod{p^u}$, but $nB_i$ is for any $i<p-1$ $\sum_{j=0}^n{j^{p-1}}=\sum_{j=0}^{p-1}{ \frac{B_j\binom{p}{j}}{p} }n^{p-j}=nB_{p-1} \pmod{p^u}$
11.12.2018 03:51
11.12.2018 11:45
Is the following correct? Suppose to the contrary that there exists prime number $p<100$ that $p\mid n$ and $n\mid 1^k+2^k+\cdots +n^k$ for all $k\leqslant 99$. Let $a=\nu_p (n)$ and $n=p^aN$. Note that $\sum_{i=1}^{p^aN}{i^k}\equiv N\sum_{i=1}^{p^a}{i^k}\pmod{p^a}$. Since $\gcd (p,N)=1$, we have $p^a\mid 1^k+2^k+\cdots +(p^a)^k$ for all $k=1,2,...,99$. For each positive integer $k$, let $S_k=1^k+2^k+\cdots +(p^a)^k$. Recall that $$(p^a+1)^k-1=\sum_{i=1}^{p^a}{(i+1)^k-i^k} =\sum_{j=1}^{k}{\binom{k}{j}\sum_{i=1}^{p^a}{i^{k-j}}}=\left( \sum_{j=1}^{k-1}{\binom{k}{j}S_{k-j}}\right) +p^a.$$In particular, plugging $k$ by $p$, we have $(p^a+1)^p-1-p^a=\sum_{j=1}^{p-1}{\binom{p}{j}S_{p-j}}$. Since $p\mid \binom{p}{j}$ and $p^a\mid S_{p-j}$ for all $j=1,2,...,p-1$, we get that $p^{a+1}\mid (p^a+1)^p-(p^a+1)$. So, $p^{a+1}\mid (p^a+1)\left( (p^a+1)^{p-1}-1\right)$. But this is false since $\nu_p \left( (p^a+1)^{p-1}-1\right) =\nu_p(p^a)=a$.
11.12.2018 12:55
ETS no prime $p<100$ divides $n$. Assume for a contradiction the opposite. Write $S_k=1^k+$...$+n^k$ and use the identity $(n+1)^p-1=\sum_{k=1}^n ((k+1)^p-k^p) =$ $\sum_{k=0}^{p-1} {p \choose k} S_k$. But $pn$ divides the LHS but not the RHS: note that $p$ divides the $\frac{LHS}{n}$ so it must also divide the $\frac{RHS}{n}$, but each term on the RHS, $\frac{{p \choose k} S_k}{n}$ is divisible by p, except for $\frac{{p \choose 0} S_0}{n}$, which is 1, contradiction.
12.12.2018 12:25
This solution is quite long. But it proves much stronger result. (In fact we only need $k=p-1$ to force $p\nmid n$.) Define polynomial $S_k(X)$ by $S_k(n) = 1^k+2^k+...+n^k$ for every $n\in\mathbb{Z}^+$. Obviously $\deg S_k = k+1$. Claim 1 : $S_k(X)$ have leading coefficient of $\tfrac{1}{k+1}$. Proof : Let $e_0,e_1, e_2,...,e_k$ be integers such that $$X^k = e_0\binom{X}{0} + e_1\binom{X}{1} + e_2\binom{X}{2} + ... + e_k\binom{X}{k}.$$Clearly $e_k=k!$. Moreover, by Hockey Stick identity, we get $$S_k(X) = e_0\binom{X+1}{1} + e_1\binom{X+1}{2} + e_2\binom{X+1}{3} + ... + e_k\binom{X+1}{k+1}$$Thus $S_k(X)$ have leading coefficient of $\tfrac{e_k}{(k+1)!} = \tfrac{1}{k+1}$ as claimed. Moreover, we also get that $(k+1)!S_k(X)$ have integer coefficients. Let $T_k(X) = (k+1)!S_k(X)$. Claim 2 : Let $p$ be a prime. Then in $\mathbb{Z}_p[x]$, we have $T_{p-1}(X) = -(X^p-X)$. Proof : Observe that in $\mathbb{Z}_p[X]$, $$T_{p-1}(X+1) - T_{p-1}(X) = p!X^{p-1} = 0$$However, $T_{p-1}(1) = p! = 0$. Thus previous equation gives $1,2,3,...,p$ are roots of $T_{p-1}$. Since $T_{p-1}(X)$ has degree $p$ and leading coefficient $(p-1)! = -1$ (Wilson), this is enough to conclude that $$T_{p-1}(X) = -(X-1)(X-2)...(X-p) = -(X^p-X)$$as claimed. Suppose that $n\mid 1^{p-1} + 2^{p-1} + ... + n^{p-1}$. Since $T_{p-1}(0) = 0$, there exists polynomial $P(X) = \frac{T_{p-1}(X)}{X}$. Therefore $$\mathbb{Z}\ni \frac{S_{p-1}(n)}{n} = \frac{T_{p-1}(n)}{p!n} = \frac{P(n)}{p!}$$However, Claim 2 implies $P(X) \equiv X^{p-1}-1\pmod p$ so $$p\mid \frac{T_{p-1}(n)}{n} \implies 0\equiv P(n) \equiv n^{p-1}-1\pmod p$$or $p\nmid n$. This is enough to conclude the problem.
12.12.2018 13:10
Let $S_t=\{1,2,3,..,t\}$.We will induct on $t$.So that our result will clear for $t=99$ $t=1:S_1={1}$ and so we must proof $n$ has no divisors in $\{2,..,t+1\}=\{2\}$ but since $n|1+2+\cdot +n=\frac{n(n+1)}{2}$ we get $2\nmid n$ Assume this hold for some $t$ and in the case of $t+1$ since $\frac{1^k + 2^k + \dots + n^k}{n}$ is integer for $k \in \{1, 2, \dots, t,t+1\}$. By induction we know that $n$ has no divisors in $\{2,3,..,t+1\}$ and we need to prove that $t+2\nmid n$. Assume for the sake of the contradiction that $t+2|n$.Then $t+2$ must be prime since otherwise for some $p<t+2$ we have $p|t+2|n$ which is impossible.Now $t+2|n|1^k + 2^k + \dots + n^k$ for $k\in \{1,2,3,..,t+1\}$.Summing up all the $1^k + 2^k + \dots + n^k$ s we get $$t+2|(t+1)+\sum_{i=2}^{i=n}(i+i^2+...+i^{t+1})=(t+1)+\sum_{i=2}^{i=n}i\frac{i^{t+1}-1}{i-1}$$Since $t+2$ is prime by fermat's theorem we get $t+2|\sum_{i=1}^{i=n}i\frac{i^{t+1}-1}{i-1}$ and so $t+2|t+1$ a contradiction
20.01.2019 03:24
rmtf1111 wrote: it follows directly from the classical baby-version of the problem which is solvable with primitive roots. Is there a place I can find this problem?
20.01.2019 13:25
let $k=1$ we have $1+2+...+n=\frac{n(n+1)}2$ divisible by $n -> \frac{n+1}2$ is a integer or $2\not| n$ claim : $v_p(1^{p-1}+2^{p-1}+....+p^{k(p-1)})=k-1$ forall odd prime $p$ when n=1 the claim hold supose the claim hold for $k-1$ we will prove that the claim also hold for $k$ cause $p$ is odd $-> p^k$ has a primitive root call it $g$ $->A=\sum_{p \not | a,a \le p^k}a^{p-1} \equiv \sum_{k=1}^{\phi(p^k)}g^{k(p-1)}=\frac{g^{\phi(p^k)(p-1)}-1}{g^{p-1}-1} (\mod p^k)$ but $p|g^{p-1}-1 -> v_p(\frac{g^{\phi(p^k)(p-1)}-1}{g^{p-1}-1})=v_p(\phi(p^k))+v_p(g^{p-1}-1)-v_p(g^{p-1}-1)=k-1$ in another hand $B=\sum_{p|a,a \le p^k}a^{p-1}=p^{p-1} \sum_{a \le p^{k-1}}a^{p-1}$ divides $p^{p-1+k-2} $ by the inductive hypothesis not that $p$ is odd so $p \ge 3-> p^k|B$ $-> v_p(1^{p-1}+2^{p-1}+....+p^{k(p-1)})=v_p(A+B)=\min(v_p(A),v_p(B))=k-1$ so the claim is also hold for $k$ by induction it hold for every $k$ suppose that $n$ has divisor between $2$ and $100->$ there exist a odd prime $p<100$ and p is divisor of $n => p-1\le 99$ let $k=p-1$ and using the claim we get $v_p(1^k+2^k+...+n^k)=v_p(n)-1<v_p(n)$ so $\frac{1^k + 2^k + \dots + n^k}{n}$ are not an integer
22.01.2019 22:24
arvind_r wrote: rmtf1111 wrote: it follows directly from the classical baby-version of the problem which is solvable with primitive roots. Is there a place I can find this problem? here https://artofproblemsolving.com/community/c6h1771971_the_sum_of_p1_integers
25.01.2019 12:56
ThE-dArK-lOrD wrote: Is the following correct? Suppose to the contrary that there exists prime number $p<100$ that $p\mid n$ and $n\mid 1^k+2^k+\cdots +n^k$ for all $k\leqslant 99$. Let $a=\nu_p (n)$ and $n=p^aN$. Note that $\sum_{i=1}^{p^aN}{i^k}\equiv N\sum_{i=1}^{p^a}{i^k}\pmod{p^a}$. Since $\gcd (p,N)=1$, we have $p^a\mid 1^k+2^k+\cdots +(p^a)^k$ for all $k=1,2,...,99$. For each positive integer $k$, let $S_k=1^k+2^k+\cdots +(p^a)^k$. Recall that $$(p^a+1)^k-1=\sum_{i=1}^{p^a}{(i+1)^k-i^k} =\sum_{j=1}^{k}{\binom{k}{j}\sum_{i=1}^{p^a}{i^{k-j}}}=\left( \sum_{j=1}^{k-1}{\binom{k}{j}S_{k-j}}\right) +p^a.$$In particular, plugging $k$ by $p$, we have $(p^a+1)^p-1-p^a=\sum_{j=1}^{p-1}{\binom{p}{j}S_{p-j}}$. Since $p\mid \binom{p}{j}$ and $p^a\mid S_{p-j}$ for all $j=1,2,...,p-1$, we get that $p^{a+1}\mid (p^a+1)^p-(p^a+1)$. So, $p^{a+1}\mid (p^a+1)\left( (p^a+1)^{p-1}-1\right)$. But this is false since $\nu_p \left( (p^a+1)^{p-1}-1\right) =\nu_p(p^a)=a$. GREAT
06.02.2019 17:40
Is this correct? It suffices to prove that $n$ has no prime divisors from $2$ to $100$ inclusive. Notice that \[ (n+1)^k - 1 = \binom{k}{k-1} \sum n^{k-1} + \binom{k}{k-2} \sum n^{k-2} + \binom{k}{k-3} \sum n^{k-3} + \dots + \binom{k}{1} \sum n^1 + \binom{k}{0} \sum 1 \]\[ \sum n^{k-1} = \frac{(n+1)^k - n - 1 - \binom{k}{k-2} \sum n^{k-2} - \binom{k}{k-3} \sum n^{k-3} - \dots - \binom{k}{1} \sum n^1 }{k } \]\[ \frac{\sum n^{k-1}}{n} = \frac{ \frac{(n+1)^k - 1}{n} - \binom{k}{k-2} \frac{\sum n^{k-2}}{n} - \binom{k}{k-3} \frac{\sum n^{k-3}}{n} - \dots - \binom{k}{1} \frac{\sum n^1}{n} - 1}{k } \]Take $k$ a prime less than $100$. Therefore, we could see that $LHS$ must be an integer by hypothesis, and $k | \binom{k}{k-2} \frac{\sum n^{k-2}}{n} + \binom{k}{k-3} \frac{\sum n^{k-3}}{n} + \dots + \binom{k}{1} \frac{\sum n^1}{n} $ Thus, \[ \frac{(n+1)^k - n - 1}{nk} \in \mathbb{Z} \]\[ \frac{(n+1)((n+1)^{k-1} - 1)}{nk} \in \mathbb{Z} \]for a prime $k < 100$. For the sake of contradiction, suppose there exists a prime number $p < 100$ which divides $n$. Then, \[ \frac{(n+1)((n+1)^{p-1} - 1)}{np} \in \mathbb{Z} \]Thus, $(p,n+1) = 1$. Thus, we have \[ v_p (np) \le v_p ((n+1)^{p-1} - 1) \]\[ v_p (n) + 1 \le v_p (n+1 - 1) + v_p (p - 1) \]\[ v_p (n) + 1 \le v_p (n) \]which is a contradiction.
18.11.2019 04:48
Treat the numerator as a polynomial in $n$. Then, we can prove a couple of properties about this polynomial that will trivialize the problem. Apologies in advance for not latexing this correctly. First, we let g_k(n) =1^{k} +2^{k} + … + n^{k}. Lemma 1: The denominators of the coefficients of g_k(n) cannot have a prime factor greater than k+1. Proof) This is directly related to how these polynomials can be derived. By binomial theorem, 1 = 1 (1 + 1)^{k+1} = k+1 C k+1 * 1^{k+1} + k+1 C k * 1^{k} + k+1 C k-1 * 1^{k-1} + … + k+1 C 1 * 1^{1} + k+1 C 0 * 1^{0} (1 + 2)^{k+1} = k+1 C k+1 * 2^{k+1} + k+1 C k * 2^{k} + k+1 C k-1 * 2^{k-1} + … + k+1 C 1 * 2^{1} + k+1 C 0 * 2^{0} (1 + 3)^{k+1} = k+1 C k+1 * 3^{k+1} + k+1 C k * 3^{k} + k+1 C k-1 * 3^{k-1} + …. + k+1 C 1 * 3^{1} + k+1 C 0* 3^{0} … (1 + n)^{k+1} = k+1 C k+1 * n^{k+1} + k+1 C k * n^{k} + k+1 C k-1 * n^{k-1} + …. + k+1 C 1 * n^{1} + k+1 C 0* n^{0} Adding side by side, and canceling like terms, we have that (n+1)^{k+1} = k+1 C k * g_k(n) + k+1 C k-1 * g_{k-1}(n) + k+1 C k-2 * g_{k-2}(n) + … + k+1 C 1 g_1(n) + (n+1). In other words, k+1 C k * g_k(n) = (n+1)^{k+1} – ( k+1 C k-1 * g_{k-1}(n) + k+1 C k-2 * g_{k-2}(n) + … + k+1 C 1 g_1(n) + (n+1)). To prove the lemma, let us induct from here. I will leave you guys to fill in the details, but it is obvious how the lemma holds from here by induction. Lemma 2: g_{p-1}(n) = 1^{p-1} + 2^{p-1} + … + n^{p-1} has leading coefficient 1/p and linear coefficient a/b for some a, b such that gcd(a, b) = 1 and v_p(b) = 1. (The constant term is 0 because g_{p-1}(0) = 0) Proof) The leading coefficient is 1/p by taking the integration. The sum approaches 1/p. The linear coefficient is t/p because in k+1 C k * g_k(n) = (n+1)^{k+1} – ( k+1 C k-1 * g_{k-1}(n) + k+1 C k-2 * g_{k-2}(n) + … + k+1 C 1 g_1(n) + (n+1)), consider the linear term. First we replace k with p-1 to see things more clearly. p * g_{p-1}(n) = (n+1)^{p} – ( p C p-2 * g_{p-2}(n) + p C p-3 * g_{p-3}(n) + … + p C 1 g_1(n) + (n+1)). Observing the linear terms, we first note that it cannot be 0. For the linear term to be 0, we need the linear term of right hand side to be 0. Simplify each rational linear coefficient and combine the fractions to add them. We know from Lemma 1 that none of its denominators are divisible by p. Therefore, while all numbers on the numerators are multiple of p but the coefficient 1 from (n+1). By this reason, the linear term cannot be 0. Lemma 2 is pretty much straightforward at this point. The sum of the rational linear coefficients of the right hand side simplified cannot have a numerator or denominator divisible by p. Therefore, dividing it by p on the left hand side, we know that the linear term is a/b for some a, b where gcd(a,b)=1 and v_p(b) = 1.
15.03.2020 02:56
We will prove that there are no primes $p < 100$ for which $p \mid n$, which is sufficient. We first show that $n$ must be odd. Suppose $2^\ell$ fully divides $n$, for some $\ell \geq 1$. Take $k = 1$. Then, we have \begin{align*} \nu_2(1^1 + 2^1 + \dots n) &= \nu_2\left(\frac{n(n + 1)}{2}\right) \\ &= \nu_2(n) + \nu_2(n + 1) - \nu_2(2) \\ &= \ell - 1 \\ &< \ell. \end{align*}Thus, $2^\ell \nmid \left(1^1 + 2^1 + \dots + n^1\right)$, contradiction. This implies that $n$ is odd, as claimed. Now, suppose there is an odd prime $p < 100$ for which $p \mid n$. Suppose $\ell = \nu_p(n)$, and let $n = p^\ell q$. We require \begin{align*} 1^k + 2^k + \dots + (p^\ell q)^k &\equiv 0 \pmod{p^\ell} \\ q\left(1^k + 2^k + \dots + (p^\ell)^k\right) &\equiv 0 \pmod{p^\ell} \\ 1^k + 2^k + \dots + (p^\ell)^k &\equiv 0 \pmod{p^\ell}, \end{align*}for all $1 \leq k \leq 99$. We claim that this is impossible for $k = p - 1$ (since $p < 100$, we have $1 \leq k = (p - 1) \leq 99$). Indeed, we will now show by induction on $\ell$ that \begin{align*} \nu_p\left(1^{p - 1} + \dots + \left(p^\ell\right)^{p - 1}\right) &= \ell - 1. \end{align*}In what follows, let $S_\ell = 1^{p - 1} + \dots + \left(p^\ell\right)^{p - 1}$. The base case, when $\ell = 1$, is true because \begin{align*} 1^{p - 1} + \dots + (p - 1)^{p - 1} + p^{p - 1} &\equiv (p - 1) \pmod{p}, \end{align*}so $\nu_p(S_1) = 0$. Now, suppose $\nu_p(S_j) = j - 1$. Let $g$ be a primitive root modulo $p^{j + 1}$; note that $g$ is also a primitive root modulo $p^r$ for any $j \leq k$. Then, notice that \begin{align*} S_{j + 1} &\equiv \sum_{i = 1}^{p^{j + 1} - p^j} g^{(p - 1)i} + p^{p - 1}S_j \pmod{p^{j + 1}} \\ &\equiv g^{p - 1} \cdot \frac{g^{(p - 1)(p^{j + 1} - p^j)} - 1}{g^{p - 1} - 1} + p^{p - 1}S_j \pmod{p^{j + 1}}. \end{align*}By induction, we have $p^{j - 1} \mid S_j$, so $p^{p - 1}S_j \equiv 0 \pmod{p^{j + 1}}$. Thus, we have \begin{align*} S_{j + 1} &\equiv \frac{g^{(p - 1)(p^{j + 1} - p^j} - 1)}{g^{p - 1} - 1} \pmod{p^{j + 1}}. \end{align*}Now, by LTE we have \begin{align*} \nu_p\left(\frac{g^{(p - 1)(p^{j + 1} - p^j} - 1)}{g^{p - 1} - 1}\right) &= \nu_p\left(g^{(p - 1)(p^{j + 1} - p^j)} - 1\right) - \nu_p\left(g^{p - 1} - 1\right) \\ &= \nu_p(g^{p - 1} - 1) + \nu_p(p^{j + 1} - p^j) - \nu_p(g^{p - 1} - 1) \\ &= j. \end{align*}Thus, it follows that $\nu_p(S_{j + 1}) = j$, completing our induction. This is enough to imply that there are no primes less than $100$ which divide $n$, which completes the proof. $\Box$
15.03.2020 08:51
Set $k=1$ to see that $n$ is odd. Let $p\ge3$ be a prime dividing $n$, and let $e=\nu_p(n)$. Then I claim \[\nu_p\left(\sum_{x=0}^{n-1}x^{p-1}\right)=e-1.\]This will prove the problem by taking $p\le100$ a prime dividing $n$. Note that \[\sum_{x=0}^{n-1}x^{p-1}\equiv\frac n{p^e}\sum_{x=0}^{p^e-1}x^{p-1}\pmod{p^e},\]so we prove $\nu_p\left(\sum_{x=0}^{p^e-1}x^{p-1}\right)=e-1$. Define \[T_k:=\sum_{\nu_p(x)=k}x^{p-1},\quad\text{so that}\quad\sum_{x=0}^{p^e-1}x^{p-1}\equiv\sum_{k=0}^eT_k\pmod{p^e}.\]If $g$ denotes a primitive root mod $p^{e-k}$, then \[T_k\equiv p^{k(p-1)}\sum_{i=0}^{\varphi(p^{e-k}-1)}g^{i(p-1)}\equiv\frac{g^{(p-1)\varphi(p^{e-k})}-1}{g^{p-1}-1}p^{k(p-1)}\pmod{p^e}.\]By Lifting the Exponent, \[\nu_p\left(g^{(p-1)\varphi(p^{e-k})}-1\right)=\nu_p\left(g^{p-1}-1\right)+e-k-1,\]so $\nu_p(T_k)=e-k-1+k(p-1)=e-1+k(p-2)$, which equals $e-1$ when $k=0$ and is at least $e$ otherwise. Thus \[\nu_p\left(\sum_{k=0}^eT_k\right)=\nu_p(T_0)=e-1,\]as desired.
20.03.2020 09:27
CantonMathGuy wrote: Let $n$ be a positive integer such that the number \[\frac{1^k + 2^k + \dots + n^k}{n}\]is an integer for any $k \in \{1, 2, \dots, 99\}$. Prove that $n$ has no divisors between 2 and 100, inclusive. Define $$S_\ell:=1^\ell+2^\ell+\dots+n^\ell,$$so that $n \mid S_\ell$ for all $\ell \in \{1,2,\dots,99\}.$ Let $p$ be a prime in $\{2,3,\dots,100\}.$ Then \begin{align*} \frac{(n+1)^p-1}{n} &=\frac{1}{n} \sum_{i=1}^n (i+1)^p-i^p \\ &=\frac{1}{n} \sum_{i=1}^n \binom{p}{1}i^{p-1}+\binom{p}{2}i^{p-2}+\dots+\binom{p}{p-1}i+1 \\ &=\left( \binom{p}{1}\frac{S_{p-1}}{n}+\binom{p}{2}\frac{S_{p-2}}{n}+\dots+\binom{p}{p-1}\frac{S_{1}}{n} \right)+1 \end{align*}Since each binomial coefficient on the right is divisible by $p,$ and each fraction is an integer by the hypothesis, hence modulo $p,$ the above gives $$\frac{(n+1)^p-1}{n} \equiv 1 \pmod{p}.$$However, if $p \mid n,$ then the left side is $$(n+1)^{p-1}+(n+1)^{p-2}+\dots+(n+1)+1 \equiv 1+1+\dots+1 \equiv 0 \not \equiv 1 \pmod{p},$$which is a contradiction. Thus, no prime in $\{2,3,\dots,100\}$ divides $n,$ so done. $\blacksquare$ Comment: The power sum formula works for $k=1,2,3,$ however we don't have any (simple) formula for $k \ge 4.$ So, we fall to first principles, which in this case is the proof of the cases $k=2,3$ which solves the problem!
11.05.2021 15:27
Does this work? First I claim that it only suffices to verify prime powers. Indeed, for a maximal prime power $p^e \mid n$, we have: $$1^k+2^k+\cdots+n^k=\frac{n}{p^e}(1^k+2^k+\cdots+p^{ek}) \pmod{p^e},$$and since $p \nmid \tfrac{n}{p^e}$ we require $1^k+2^k+\cdots+p^{ek} \equiv 0 \pmod{p^e}$ for the original expression to be an integer, as desired. Now it clearly suffices to prove that for any power of an arbitrary fixed prime $p \in \{2,\ldots,99,100\}$, the expression is not an integer. With $k=1$ we can immediately eliminate powers of two. Hence suppose that $p \neq 2$. I will now prove that if $k=p-1$, then the expression is never an integer no matter the exponent, with induction on $e$. The base case is clear by Fermat's little theorem. Now suppose that we have: $$1^{p-1}+2^{p-1}+\cdots+(p^e)^{p-1} \not\equiv 0 \pmod{p^e},$$And we wish to show that: $$1^{p-1}+2^{p-1}+\cdots+(p^{e+1})^{p-1} \not\equiv 0 \pmod{p^{e+1}},$$where $e$ is a positive integer. The key claim here is as follows: Claim: We have the congruency: $$1^{p-1}+2^{p-1}+\cdots+(p^e)^{p-1} \equiv (rp^e+1)^{p-1}+(rp^e+2)^{p-1}+\cdots+(rp^e+p^e)^{p-1} \pmod{p^{e+1}},$$where $r \in \{1,2,\ldots,p-1\}$. Proof: Observe that by the binomial theorem, we have: $$(rp^e+a)^{p-1} \equiv (p-1)rp^ea^{p-2}+a^{p-1}.$$Hence subtracting $1^{p-1}+2^{p-1}+\cdots+(p^e)^{p-1}$ from both sides, it suffices to show that: \begin{align*} \sum_{i=1}^p (p-1)rp^ei^{p-2} &\equiv 0 \pmod{p^{e+1}}\\ \sum_{i=1}^p (p-1)ri^{p-2} &\equiv 0 \pmod{p}\\ \sum_{i=1}^{p} i^{p-2} &\equiv 0 \pmod{p}. \end{align*}But it is well-known that we have: $$1^k+2^k+\cdots+p^k \equiv f(k) \pmod{p},$$where $$f(k)=\begin{cases}0 & p-1 \nmid k\\ -1 & p-1 \mid k,\end{cases}$$which can be proven with primitive roots. Since $p \neq 2$, $p-2$ is positive, so for size reasons we cannot have $p-1 \mid p-2$. As such $1^{p-2}+2^{p-2}+\cdots+p^{p-2} \equiv 0 \pmod{p}$ as desired. Now we return to the original problem. Note that, unconditionally: $$1^{p-1}+2^{p-1}+\cdots+(p^{e+1})^{p-1}=\sum_{i=1}^{p-1}\sum_{j=1}^{p^e} (ip^e+j)^{p-1},$$and by the claim we have: $$\sum_{i=1}^{p-1}\sum_{j=1}^{p^e} (ip^e+j)^{p-1}\equiv p\sum_{j=1}^{p^e} (p^e+j)^{p-1}.$$As we have: $$1^{p-1}+2^{p-1}+\cdots+(p^e)^{p-1}=\sum_{j=1}^{p^e} (p^e+j)^{p-1}\not\equiv 0 \pmod{p^e},$$it follows that: $$1^{p-1}+2^{p-1}+\cdots+(p^{e+1})^{p-1}\not\equiv 0 \pmod{p^{e+1}},$$as desired. This completes the induction, so no primes $p \in \{2,3,\ldots,100\}$ work, and we're done. $\blacksquare$
15.01.2022 21:02
Lemma: $n\nmid 1^k+2^k+\ldots+n^k$ for any $k\in \{0,1,2,\ldots,p-1\}$, where $p$ is the smallest prime dividing $n$. Proof: Suppose for the sake of contradiction that $n\mid 1^k+2^k+ \ldots+n^k$. Then for any polynomial $f(y)$ in $\mathbb{Z}[y]$ with degree less than $p$ satisfies $\sum_{i=1}^n f(i)\equiv 0\pmod n$. Consider the polynomial $P(y)=(y-1)(y-2)(y-3)\cdots(y-(p-1))$. We have\[\sum_{j=1}^n P(j)= (p-1)!\sum_{j=1}^n \binom{j-1}{p-1}=(p-1)!\binom{n}{p}\]must be $0\pmod n$. Now we have\[\nu_p\left((p-1)!\binom{n}{p}\right)=\nu_p\left(\binom{n}{p}\right)=\nu_p\left(\frac{n(n-1)(n-2)\cdots(n-(p-1))}{p!}\right)=\nu_p(n)-1\]So $(p-1)!\binom{n}{p}\not\equiv 0\pmod n$. $\blacksquare$ Thus, if $p<101$, then there is a contradiction. So $p\ge 101$, which solves the problem.
16.01.2022 22:00
I am slightly surprised that no one has yet posted the following solution (while, as several solutions show, just one value of $k$ for each prime suffices, we might as well use all values of $k$ that we are given): It clearly suffices to prove the following: If $p$ is a prime number and $n$ is such that \[n \mid 1^k+2^k+\dots+n^k\]for all $k \le p-1$, then $p$ does not divide $n$. Now just note that $(p-1)! \binom{x}{p-1}$ is a polynomial in $x$ with integer coefficients, and of degree $p-1$, hence \[n \mid (p-1)! \left( \binom{1}{p-1}+\dots+\binom{n}{p-1}\right)=(p-1)! \cdot \binom{n+1}{p}=\frac{(n+1)n(n-1)\dots (n-p+2)}{p}\]so that $p$ divides $(n+1)(n-1)(n-2)\dots (n-p+2)$ which clearly implies $p \nmid n$.
16.01.2022 22:53
Tintarn wrote: I am slightly surprised that no one has yet posted the following solution Very excellent and nice
21.01.2022 09:49
Suppose $p$ is such that $p < 100, p | n$ and let $z = v_p(n)$. Note that $(r+1)^k - r^k = \sum_{i=0}^{k-1} \binom{k}{i} r^i$, summing this from $r = 1$ to $n$ and taking $k = p$, we have $$(n+1)^{p} - 1 = \sum_{m=1}^{n} \sum_{i=0}^{p-1} \binom{p}{i} m^i$$But the problem says that $n | \sum_{m=1}^n m^i$ for any $i < 100$. Therefore, (since $p < 100$) we have that each individual term is divisible by $n$, on the RHS, but note that in addition, for all $i > 0$, we have $p | \binom{p}{i}$, so apart from the last term, which is just $n$, $p^{z+1}$ divides each other term. Therefore, we have $$(n+1)^p - 1 \equiv n \pmod {p^{z+1}}$$but this actually can't happen because $v_p$ of the RHS is $z$ while the $v_p$ of the LHS is $v_p(n) + v_p(p) = z+1$ by LTE, a contradiction. Therefore, any prime divisor of $n$ must be $> 100$, which finishes the problem. $\blacksquare$
08.07.2024 20:43