INTRODUCING 5 - days-a-week problem solving session for Math Olympiad and ISI Entrance. Learn More 

October 21, 2018

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

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
JOIN TRIAL
support@cheenta.com