Suppose $N$ is a large integer and let $k$ be an integer s.t. $k > N$. Under what conditions can we conclude that $1^N, 2^N, \ldots, k^N$ are all divisors of $k!$?
Determining when $1^N, 2^N, \ldots, k^N$ are divisors of $k!$
3
$\begingroup$
real-analysis
elementary-number-theory
-
0Is this ever true? If k is prime, then ${k^N}$ will never be a divisor of k!, right? – 2012-08-30
-
0It is always true for $N = 1$, right? Even though $1$ would not be called a large integer... Now consider the largest prime $p$ not exceeding $k$. Only $p^1$ can be a divisor of $k!$, while $p^2, p^3, \ldots, p^N$ cannot be divisors of $k!$, right? So your desired result cannot hold for $N > 1$. – 2012-08-30
-
1Your last statement there is correct, and if one of $k-1, k-2, \dots ,k/2$, is a prime, you are going to struggle to get them all as divisors, for large $N$. In fact, by [Bertrand's postulate](http://en.wikipedia.org/wiki/Bertrand's_postulate), it is probably not difficult to prove that it is never true, at least for $N\geq 2$. – 2012-08-30
1 Answers
5
Trivially, the result is true for $N=1$, so consider the case where $N\geq 2$.
Suppose $k$ is even, then by Bertrand's Postulate, there is a prime $p$ satisfying $k/2 < p < k$, so that $2p > k$, and it follows that $p$ is a factor of $k!$, but $p^2$ is not, since there is only one multiple of $p$ amongst the numbers $1, 2, \dots, k$.
A similar argument works if $k$ is odd, say $k=2m+1$, since there is then at least one prime satisfying $m+1 < p < 2m+2$.
-
0What if we had $1,3,5, \ldots ,2k + 1$ instead of ${1^N},{2^N}, \ldots ,{k^N}$? – 2012-08-30
-
0Not sure yet - but again, there probably has to be a prime in the second half of that list which is not a factor of $k!$. What is the origin of the problem? (Looks a bit like you might be trying some algorithm involving factorising). – 2012-08-30
-
0It just relates to some infinite series. – 2012-08-31