# Finding such that $xyz \equiv k \pmod{n}$, where $k, n$ are known?

What is an efficient way to choose three numbers $$x, y, z$$ such that $$xyz \equiv k \pmod{n}$$, where $$k, n$$ are given?

I was thinking about choosing $$x$$ and $$y$$ randomly and then computing an inverse for $$z$$; however, I realized that there's no guarantee that this inverse exists. So, I'm not so sure if this is an efficient way anymore.

Note that I don't want to just choose three random numbers and see if their product is congruent to $$x$$ (and try again if not). I'm wondering if there's some efficient way to do this.

• Random in what set? There is no such thing as a "random number" per se. – Robert Israel Apr 19 at 0:35
• I just want a good/reliable way to generate such $x, y, z$ without many trial/errors. So I guess random is bad terminology here. – user663014 Apr 19 at 0:39
• "Efficient" does not have a precise meaning. If you edit the question to tell us why you need this algorithm, how large $n$ is likely to be, how $k$ is chosen and what kind of time constraints you have we may be able to help. – Ethan Bolker Apr 19 at 1:06
• If by 'random' you mean that the numbers are to be chosen arbitrarily (without recourse to method), then the notion of any algorithmic method (efficient or otherwise) has been ruled out. I think you want a method, but it's not clear what sorts of methods you wish to exclude. – Keith Backman Apr 19 at 2:02

Let's say you want $$x, y, z$$ to be in the integers mod $$n$$. The simplest case is if $$\gcd(k,n)=1$$. Then $$x$$ and $$y$$ can be anything coprime to $$n$$, and $$z \equiv k(x y)^{-1} \ (\bmod n)$$.
More generally, suppose $$gcd(k,n) = g > 1$$. Then take any $$g_1, g_2, g_3$$ so that $$g = g_1 g_2 g_3$$, any $$h_1, h_2$$ coprime to $$n/g$$, let $$h_3 \equiv (k/g) (h_1 h_2)^{-1} \ (\bmod (n/g)$$, and take $$x = g_1 h_1$$, $$y = g_2 h_2$$, $$z = g_3 h_3$$.