There is no need to limit the better approach to the case when k is prime — a generalization is possible for any k.

Let k = n/x. Because n%x == 0, k is an integer. We have (as you said) that n = xk => n+1 = xk+1 => xk+1 $$$\equiv$$$ 0 (mod y) => xk $$$\equiv$$$ -1 (mod y) => x * (-k) $$$\equiv$$$ 1 (mod y).

If x and y are not coprime ( which can be found with euclid's algorithm in O(log(min(x, y))) ), there is no integer "i" that satisfies x * i $$$\equiv$$$ 1 (mod y). So, there is no possible n.

If, however, x and y are coprime, we can apply various theorems to quickly get to a result.

Let "z" be x's modular inverse with respect to y (i.e. the unique number which satisfies 0 <= z < y and x * z $$$\equiv$$$ 1 (mod y)). "z" can be calculated in O(log(min(x, y))) with the extended euclidean algorithm or with a higher complexity using Euler's theorem: $$$x^{\phi (y)} \ \equiv \ 1 \ (mod \ y)$$$.

Now, we have that x * z $$$\equiv$$$ 1 (mod y) => x * (-(-z)) $$$\equiv$$$ 1 (mod y) => x * (-z) $$$\equiv$$$ -1 (mod y) => x * (-z) + 1 $$$\equiv$$$ 0 (mod y) => (x * (-z) + 1) % y == 0.

Summary: in the case of x and y coprime, we have that (x * (-z)) % x == 0 and (x * (-z) + 1) % y == 0. Therefore, "x * (-z)" is a possible and valid choice of n. If, by any chance, it's negative and you don't like it, you can always increase it by a multiple of lcm(x, y). If, by any chance, it's too large, you can decrease it by a multiple of lcm(x, y).

Total time complexity: O(log(min(x, y)))