Тождество n div k^2 = (n div k) div k

[IgorSukharev]

Здравствуйте! При разработке одного алгоритма я использовал нижеприведённое тождество как заведомо истинное. Сейчас понимаю, что нужно его доказать, но у меня недостаточно навыков для этого.
Тождество. Для любых целых положительных чисел $n$ и $k$ верно:
$n \operatorname{div} k^2 = (n \operatorname{div} k) \operatorname{div} k$,
где $\operatorname{div}$ — оператор деления нацело (как в Паскале).
Прошу помочь с доказательством.

[Pphantom]

Представьте $n$ как $n=a \cdot k^2 + b \cdot k + c$ (какими могут быть коэффициенты?) и проверьте, чему равны обе части равенства.

[IgorSukharev]

Спасибо! Вот мои выкладки.
Представим $n$ в виде $ak^2 + bk + c$, где $a, b, c$ — целые неотрицательные числа.
Найдём максимально возможное $a$, при котором возможно такое представление. Так как $n \geqslant ak^2$, то
$a_{\max} = n \operatorname{div} k^2$.
При $a = a_{\max}$ найдём максимально возможное $b$, при котором возможно такое представление. Так как $n \geqslant ak^2 + bk$, то
$bk \leqslant n - ak^2 = n \operatorname{mod} k^2$,
$b_{\max} = (n \operatorname{mod} k^2) \operatorname{div} k$.
При $a = a_{\max}, b = b_{\max}$
$c = n \operatorname{mod} k$,
так как $n = (ak + b)k + c$, а если $c \geqslant k$, то из $с$ можно вычесть $k$ и добавить $1$ к $b$, что противоречит условию $b = b_{\max}$.

Итого,

$$n = (n \operatorname{div} k^2)k^2 + ((n \operatorname{mod} k^2) \operatorname{div} k)k + n \operatorname{mod} k.$$

Поделив на $k$ нацело, получим:

$$n \operatorname{div} k = (n \operatorname{div} k^2)k + ((n \operatorname{mod} k^2) \operatorname{div} k,$$

так как $n \operatorname{mod} k$ не делится на $k$.
Поделив на $k$ нацело ещё раз, получим:

$$\fbox{(n \operatorname{div} k) \operatorname{div} k = n \operatorname{div} k^2},$$

так как
$n \operatorname{mod} k^2 < k^2$,
$((n \operatorname{mod} k^2) \operatorname{div} k < k$,
а значит, $((n \operatorname{mod} k^2) \operatorname{div} k$ не делится на $k$.
Мы получили искомое тождество.

[Pphantom]

IgorSukharev в сообщении #1535289 писал(а):

Найдём максимально возможное $a$, при котором возможно такое представление.

А зачем, собственно? Я уж не говорю о том, что найти его не получится...

В основном-то вы сделали все нормально, но только представить это можно намного проще. Эти коэффициенты - попросту разряды в представлении $n$ в системе счисления с основанием $k$ ($b$ и $c$ - без каких-либо оговорок, $a$ - с оговорками, поскольку в него простоты ради "засунуты" заодно и все более старшие разряды). Отсюда сразу же следует существование и единственность такого представления, а заодно то, что $0 \leqslant b < k$ и $0 \leqslant c < k$.

[IgorSukharev]

Если представить $a$ в $k$-ичной позиционной системе счисления, то получится число $\overline{\dots a_2 a_1 a_0}_k$. Как известно,
$\overline{\dots a_{n+1} a_n \dots a_1 a_0}_k \operatorname{div} k^n = \overline{\dots a_{n+1} a_n}_k.$
В свете этого тождество становится очевидным.

[Pphantom]

IgorSukharev в сообщении #1535293 писал(а):

В свете этого тождество становится очевидным.

Именно.