Обсуждение: Длинное деление

---

Доказательство в статье мне не кажется ясным. Это не доказывает того факта, что . Кроме того, почему он не использует евклидово деление ?${\ Displaystyle \ бета _ {я} <b}$

${\ Displaystyle d_ {я}}$можно разделить на , см. Евклидово деление . Значит существуют и такие, что и . Если это показать , то мы нашли и как и .${\ Displaystyle м}$${\ Displaystyle д}$${\ Displaystyle г}$${\ displaystyle d_ {i} = mq + r}$${\ Displaystyle 0 \ Leq г <м}$${\ Displaystyle д <Ь}$${\ Displaystyle \ бета _ {я}}$${\ Displaystyle г_ {я}}$${\ Displaystyle \ бета _ {я} = д}$${\ Displaystyle г_ {я} = г}$

Будем действовать по индукции. At , образован первыми цифрами , поэтому он имеет цифры, что является общим количеством цифр . Тогда не может быть больше или равно , так как было бы числом с или большим количеством цифр, и это было бы . Это противоречит . Итак, у нас должно быть .${\ Displaystyle я = 0}$${\ Displaystyle d_ {я}}$${\ Displaystyle л + 1}$${\ Displaystyle п}$${\ Displaystyle л + 1}$${\ Displaystyle м}$${\ Displaystyle д}$${\ Displaystyle б}$${\ Displaystyle кв.м.}$${\ Displaystyle л + 2}$${\ Displaystyle d_ {я} <qm}$${\ Displaystyle г \ geq 0}$${\ Displaystyle д <Ь}$

Теперь предположим с . Тогда по определению . То есть сдвигается влево с добавлением цифры на новое место справа. Так как , количество цифр меньше или равно таковым из , то есть . Сложнее всего проверить, когда его цифры точно равны . Запишем цифры , и${\ Displaystyle d_ {я} = м \ бета _ {я} + r_ {я}}$${\ Displaystyle 0 \ leq r_ {я} <м}$${\ Displaystyle d_ {я + я} = br_ {я} + \ альфа _ {я + 1 + л}}$${\ Displaystyle d_ {я + 1}}$${\ Displaystyle г_ {я}}$${\ Displaystyle \ альфа _ {я + 1 + л}}$${\ Displaystyle г_ {я} <м}$${\ Displaystyle г_ {я}}$${\ Displaystyle м}$${\ Displaystyle л + 1}$${\ Displaystyle л + 1}$${\ Displaystyle г_ {я}}$${\ Displaystyle d_ {я + 1}}$${\ Displaystyle м}$

где мы предполагаем, что некоторые начальные цифры и могут совпадать, но наверняка в какой-то момент какая-то цифра должна отличаться и, в частности, так как . Обратите внимание, что здесь l+2 цифры.${\ Displaystyle г_ {я}}$${\ Displaystyle м}$${\ Displaystyle с <т}$${\ Displaystyle г_ {я} <м}$${\ Displaystyle d_ {я + 1}}$

---