Если числа а и b заведомо делятся друг на друга, то можно воспользоваться версией метода Ньютона в р-адической арифметике. В дальнейшем будем считать р простым числом. Если b делится на 
, то его последние k разрядов равны 0. Поскольку а делится на b, то а делится на . Отбрасывая последние k нулевых разрядов чисел а и b, приходим к задаче деления, где b не делится на р. Так как р — простое число и 
, то наибольший общий делитель 
и р равен 1. Расширенным алгоритмом Евклида найдем числа u и v, что 
. Положим 
. Далее проводим итерации метода Ньютона, вычисляя 
по формуле 
. Поскольку р — основание системы счисления, то, по сути, мы проводим операции над младшими 2k разрядами, отбрасывая старшие. Обозначим через 
величину 
. Индукцией по k покажем сравнение 
. При k=0 имеем: 
. Пусть 
. Тогда, 
.
Единственным решением сравнения 
является частное а/b. Поэтому, не более чем через 
итерацию метода, частное будет найдено. Трудоемкость метода Ньютона в этом случае не превосходит O( 
) . Если для умножения используется быстрое преобразование Фурье, то трудоемкость метода в этом случае оценивается величиной 
. Как видим, за счет более экономной схемы умножения, трудоемкость деления чисел нацело, по порядку, имеет ту же трудоемкость, что и умножение.
Тем самым доказана
Теорема. Трудоемкость деления чисел без остатка ограничена сверху величиной 
.
