Friend's Beautiful Problem

Suppose that x x is an integer such that x m x^m is divisible by m ! m! for a positive integer m m . Is it true that for all positive integers n < m n<m , then x n x^n is divisible by n ! n! ?

Yes No

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Brian Moehring
Jul 2, 2018

Note: Every time I use the vertical bar | , it will mean "divides".

Let p p be a prime, let n n be any positive integer, and let α \alpha be any non-negative integer. Then p α n ! α k = 1 n p k k = 1 n p k k = 1 n 2 k = n . p^\alpha|n! \implies \alpha \leq \sum_{k=1}^\infty \left\lfloor\frac{n}{p^k}\right\rfloor \leq \sum_{k=1}^\infty \frac{n}{p^k} \leq \sum_{k=1}^\infty \frac{n}{2^k} = n. Therefore n ! n! divides \substack p n p prime p n \displaystyle \prod_{\substack{p \leq n \\ p \text{ prime}}} p^n

Now consider x x and m m as in the problem. For any prime p m p \leq m , we have p m ! x m p x m p x p | m! | x^m \implies p | x^m \implies p | x Therefore, if n < m n < m , then n ! \substack p n p prime p n \substack p m p prime p n x n n ! x n n! \Big| \prod_{\substack{p \leq n \\ p \text{ prime}}} p^n \Big| \prod_{\substack{p \leq m \\ p \text{ prime}}} p^n \Big| x^n \implies n! | x^n \qquad \qquad \square

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...