nt.number theory - Reducing two variable linear Diophantine equation to modular inversion

I'm in the field of secure multiparty computation using Homomrphic encryption or secret sharing. I want to implement a secure protocol to compute the GCD of two encrypted numbers.

To calculate the GCD, I particularly need to be able to securely calculate the quotient of the division of two numbers. There is a secure protocol for that but is too expensive. Instead, I thought that I might use the much cheaper protocol for computing the modular inversion of an encrypted number as a building block for the GCD protocol.

Since both problems (quotient and modular inversion) can be reduced to solving a linear Diophantine equation then perhaps we can reduce one to the other:

Modular inversion $y=x^{-1} mbox{ mod } p$:

$x y + p m = 1$

Quotient division $q=lfloor frac{a}{b} rfloor$:

$ q b + (a mbox{ mod } b) t = a$

The question is whether we can rephrase this equation such that the right hand side is 1 (and still be a linear Diophantine), so we are able to use an existing modular inversion protocol to calculate the quotient division.

P.S.: I can't use the extended euclidean algorithm directly on any of them. The only allowed (secure) protocols to be used as building blocks are modular inversion, multiplication, modular division, and addition.