The algorithm is very nice. But I think you should think about what it means to divide one integer by another. The quotient of that operation is an integer. The remainder is an integer.
Can you express the number in terms of the quotient and remainder?
Using this expression write an algorithm that outputs the quotient and remainder using only addition, multiplication and checking equality with integers.
I think doing this would make the algorithm seem less surprising.
I still find it remarkable, that you can avoid divisions, while not to computing all multiples up-front and marking the results in a large table.