in reply to
Re: A bad shuffle

in thread A bad shuffle

*N*^{N-1}/(*N*-1)! is not an integer for any integer *N* > 2, so it is not the case that *N*! | *N*^{N}, except for *N*=1 and *N*=2.

the lowliest monk

**Update:** Here's a proof of the assertion made above. I'm sure there are better proofs of it, but this is the best I could come up with.

Assume that *N* > 2, and let *p* be the largest prime in the prime factorization of *N*. There are three cases to consider. Suppose first that *p* is 2. Then, by assumption, *N* is a power of 2 greater than or equal to 4. Therefore, 3 is a factor of *N*!, and consequently *N*! does not divide *N*^{N}. Next, suppose that *p* > 2. If *N* = *p*^{k} for some nonnegative integer *k*, then *N* is odd and not divisible by *N*! whose prime factorization includes 2. This leaves the case in which *p* > 2, and is not the sole prime factor of *N*. In this case *N* >= 2 *p*. By Bertrand's postulate there exists a prime *q* such that *p* < *q* < 2 *p* <= *N*. Therefore, there is a factor of *N*!, namely *q*, that does not divide *N*^{s}, for any positive integer *s*. Therefore, *N*! does not divide *N*^{N}, for all *N* > 2.