Exercise 1.3.51* (Largest integer divisible by all integers less than its square root.)

Question

Show that $24$ is the largest integer divisible by all integers less than its square root.

(Hint: Consider the highest power of $2$, of $3$, of $5$, of $7$ less that the square root.)

Richard Ganaye · Accepted Answer

\begin{proof} 
The positive integers less than the square root of $24$ are $1,2,3,4$, and $24$ is divisible by all these integers.

Let $n\geq 25$. Consider the highest powers of $2$, of $3$, of $5$, of $7$ less that the square root:
 \begin{align*}
 &2^s < \sqrt{n} \leq 2^{s+1},\
 &3^t <\sqrt{n} \leq 3^{t+1},\
 &5^u <\sqrt{n} \leq 5^{u+1},\
 &7^v <\sqrt{n} \leq 7^{v+1}.
  \end{align*}
  
  Suppose that $n$ is divisible by all integers less than its square root. Then $n$ is divisible by $2^s$, $3^t$, $5^u$, $7^v$, therefore
  $$2^s 3^t 5^u 7 ^ v \mid n,$$
a fortiori $2^s 3^t 5^u 7 ^ v \leq n$. Therefore
$$ n^2 = (\sqrt{n})^4 \leq 2^{s+1} 3^{t+1} 5^{u+1} 7^{v+1} = 210 	imes2^s 3^t 5^u 7^v\leq 210\, n.$$
This implies $n\leq 210$, so every integer greater than $210$ is not divisible by all integers less than its square root.

Its remains the integers $n$, where $25 \leq n \leq 210$, for which we verify the same property with a computer program, which returns all integers $n$ up to $210$ divisible by all integers less than $\sqrt{n}$.

\begin{verbatim}
def verif(maxi):
    l = []
    for n in range(1,maxi + 1):
        test = True
        i = 1
        while test and i * i < n:
            if n % i != 0:
                test = False
            i = i + 1
        if test:
            l.append(n)
    return l
    
verif(210)
                          [1, 2, 3, 4, 6, 8, 12, 24]
\end{verbatim}
So $24$ is the largest integer divisible by all integers less than its square root.
\end{proof}

Note: there is another solution using the fact that $n$ is divisible by $\lfloor \sqrt{n} floor - 1, \lfloor \sqrt{n}  floor -2, \lfloor \sqrt{n} floor - 3$, but not shorter.

Exercise 1.3.51* (Largest integer divisible by all integers less than its square root.)

Answers

Comments

Exercise 1.3.51* (Largest integer divisible by all integers less than its square root.)

Answers

Comments

Add answer