Parity and Symbolic Divisibility - an excursion in Number Theory

Consider the following problem:

Problem

Show that there do no exist non-negative integers k and m such that ( k! + 48 = 48(k+1)^m )

Discussion

Claim 1: \( k \geq 9 \)

If there are such integers then ( k! = 48 \times ((k+1)^m - 1 )).

Expanding we have ( k! = 48 \times (k^m + m \cdot k^{m-1} + {m \choose 2} k^{m-2} + \cdots + {m \choose {m-2}} k^2 + {m \choose {m-1} } k + 1 - 1 ) )

Hence ( k! = 48k\times ( k^{m-1} + m \cdot k^{m-2} + {m \choose 2} k^{m-3} + \cdots + {m \choose {m-2}} k + {m \choose {m-1} } ) )

Dividing by k on both sides we have ( (k-1)! = 48\times ( k^{m-1} + m \cdot k^{m-2} + {m \choose 2} k^{m-3} + \cdots + {m \choose {m-2}} k + {m \choose {m-1} } ) ) ... (equation (1) - we will use this again later)

This implies 48 divides (k-1)! or ( (k-1) \geq 6 \Rightarrow k \geq 7 )

In fact, we can quickly check that k = 7 and k = 8 does not work. After all, for k = 7, ( \frac{7!}{48} + 1 = 105 + 1 = 106  ) is not ( 8^m ) for any m. Similarly for k = 8, ( \frac{8!}{48} + 1 = 840 + 1 = 841  ) is not ( 9^m ) for any m.

Claim 2: k is even

( \frac{k!}{48} + 1 = (k+1)^m )

Since ( k > 8 ), then ( \frac{k!}{48} = \frac{1\times 2 \times 3 \times \cdots \times 8 \times \cdots k}{48} = 840 \times \cdots \times k ). Hence ( \frac{k!}{48} ) is even (as it is a multiple of 840). This implies ( \frac{k!}{48} + 1 ) is odd.

But that means ( (k+1)^m ) is odd or k+1 is odd. Hence k is even.

Let ( k = 2k_1 ).

Claim 3: k divides \( \frac {(k-1)!}{48} \)

We need to show that ( \frac {(k-1)!}{48} ) is divisible by 2 and (k_1 ). Since we showed ( k \geq 9 ) in claim 1, and then showed k is even; this implies k is at least 10 or more.

( \frac {(k-1)!}{48} \ = \frac {1 \times 2 \times 3 \times \cdots \times 9 \times \cdots \times (k-1)} {48} \ = 1 \times 5 \times 3 \times 7 \times 8 \times 9 \times \cdots \times (k-1) )

For k = 10, we see that (1 \times 5 \times 3 \times 7 \times 8 \times 9 ) is easily divisible by 10 (5 exists and 8 supplies one 2).

For k = 12, we see that (1 \times 5 \times 3 \times 7 \times 8 \times 9 \times 10 \times 11 ) is also divisible by 12 (3 exists and 8 supplies one 4).

From k=14 onwards, this will be trivially true because: ( k/2 \geq 7 ) will be present in the product (as it is not canceled off by division by 48), and another 2 will be supplied by the first even number that follows k/2. (There will be one such even number, because ( \frac{k}{2} + 2  \leq k-1) as ( 6 \leq k ) (in fact it 6 is much less than k as we have reached 14 or more).

Claim 4: k divides m

From Equation 1, we have:

( (k-1)! = 48\times ( k^{m-1} + m \cdot k^{m-2} + {m \choose 2} k^{m-3} + \cdots + {m \choose {m-2}} k + {m \choose {m-1} } ) )

This implies ( \frac {(k-1)!}{48} = k \times (k^{m-2} + m \cdot k^{m-3}  + \cdots + {m \choose {m-2}} )  +  m )

Therefore ( \frac {(k-1)!}{48} - k \times (k^{m-2} + m \cdot k^{m-3}  + \cdots + {m \choose {m-2}} )  =   m )

From Claim 3 we know k divides ( \frac {(k-1)!}{48} ). Hence the LHS of the above equation is divisible by k. This implies RHS is also divisible by k. Hence k divides m.

Let ( m = Qk ) where Q could be 1.

Claim 5: k cannot divide m (hence contradiction)

Use A. M. - G.M. Inequality to establish:

$$ \frac { 1+ 2 + \cdots + k}{k} > (1 \times 2 \times 3 \times \cdots \times k ) ^{\frac{1}{k}} $$

Strictly inequality holds, as the numbers are not all equal. This implies:

$$ \frac { (k+1)^k}{2^k}  > k! $$

Therefore ( \frac { (k+1)^k}{2^k} + 48  > k! + 48  ) ... (2)

Clearly ( 48 (k+1)^k > \frac { (k+1)^k}{2^k} + 48  ) ... (3).

Why? Divide both sides by ( (k+1)^k ). Then you have  ( 48 > \frac { 1}{2^k} + \frac{48}{(k+1)^k}   ). k is 9 or more, right hand sides is (much) smaller than 1. Hence 48 is certainly greater than RHS.

Combining (2) and (3) we have (  48 (k+1)^k  > k! + 48 ). Since k divides m we have ( 48 (k+1)^m > 48 (k+1)^k  > k! + 48 ).

Conclusion

Even before we start working on this problem, we should check some basic cases (where k and m are small; that is 0, 1, 2 etc.).

Also see

Advanced Math Olympiad Course at Cheenta