# A special euclidean division function

Hello,

I’m currently doing my homework about great integers. A great integer is represented with a int list. For example: the int 452 is represented by [2; 5; 4].
Also, a new type is defined with type nat = int list;;.
So, I made the following functions: addition, substraction, equality test, every comparison tests, multiplication, power, factorial.
I can use them (especially the substraction one) in the last function which I have to do: the euclidean division.
Indeed, I must create a nat -> nat -> nat*nat function with 2 great integers n and m in argument and which returns the couple (q, r) : the quotient and the remainder of the Euclidean division of n by m.
Oh, and very very important: I must code this program as we learnt at primary school, so I can’t repeat a lot of substraction or use modulo only (but I can use them!).

I really don’t know how to start…
I tried to make some plans on rough draft.
For example, with 4731//31 : We have [1; 3; 7; 4] /// [1; 3] ( (///) is the Euclidean division function).
So, do I need to take the last elements of the lists?

I hope somebody will have an idea and will be able to help me.

Thank you,
Koelite.