Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!$?

share|improve this question
    
Is this ever true? If k is prime, then ${k^N}$ will never be a divisor of k!, right? –  glebovg Aug 30 '12 at 19:07
    
It 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$. –  Dilip Sarwate Aug 30 '12 at 19:14
1  
Your 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, it is probably not difficult to prove that it is never true, at least for $N\geq 2$. –  Old John Aug 30 '12 at 19:16
add comment

1 Answer

up vote 5 down vote accepted

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

share|improve this answer
    
What if we had $1,3,5, \ldots ,2k + 1$ instead of ${1^N},{2^N}, \ldots ,{k^N}$? –  glebovg Aug 30 '12 at 19:44
    
Not 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). –  Old John Aug 30 '12 at 19:46
    
It just relates to some infinite series. –  glebovg Aug 31 '12 at 20:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.