Almost divisible by all 2

Find the largest integer n n such that n n is divisible by all positive integers less than n \sqrt{n} .


The answer is 24.

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

Leonel Castillo
Jul 1, 2018

Let's first suppose that n = k 2 n=k^2 . Then it must be that k 2 0 m o d k 1 k^2 \equiv 0 \mod k-1 , but k 2 1 m o d k 1 k^2 \equiv 1 \mod k-1 so a perfect square never has this property for k > 2 k > 2 . (It works for k=1 trivially and for k=2 because 1 0 m o d 1 1 \equiv 0 \mod 1 ).

Let's now suppose that k 2 < n < ( k + 1 ) 2 k^2 < n < (k+1)^2 . Then we must have that k n k | n and k 1 n k-1 | n . Because gcd ( k , k 1 ) = 1 \gcd(k,k-1) = 1 , it must be that n n is a multiple of k ( k 1 ) k(k-1) (assuming k > 1 k>1 ). We can now consider the question of how many multiples of k ( k 1 ) k(k-1) can be between k 2 k^2 and ( k + 1 ) 2 (k+1)^2 . Let's consider two cases:

First n = k ( k 1 ) n = k(k-1) . This does not work because k ( k 1 ) < k 2 k(k-1) < k^2 .

Second, n = 2 k ( k 1 ) n = 2k(k-1) . Then 2 k ( k 1 ) < ( k + 1 ) 2 2 k 2 2 k < k 2 + 2 k + 1 k 2 4 k < 1 ( k 2 ) 2 < 5 k 2 2 k 4 2k(k-1) < (k+1)^2 \iff 2k^2 - 2k < k^2 + 2k + 1 \iff k^2 - 4k < 1 \iff (k-2)^2 < 5 \iff k-2 \leq 2 \iff k \leq 4 . So for k > 4 k>4 there are no solutions, and because we are looking the biggest solution, we must only check k = 4 k=4 . Here k ( k 1 ) = 12 , 2 k ( k 1 ) = 24 , 3 k ( k 1 ) = 36 k(k-1) = 12, 2k(k-1) = 24, 3k(k-1) = 36 . Only 24 24 satisfies the inequalities, and we can quickly check that indeed 1 , 2 , 3 , 4 24 1,2,3,4 | 24 .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...