### maybesomeone's blog

By maybesomeone, history, 2 months ago,

how to find n such that n % x == 0 and (n + 1) % y == 0 ?

• +6

 » 2 months ago, # | ← Rev. 2 →   +9 n % x = 0 => n = xk => n+1 = xk + 1 => xk (mod y) = y-1 => (x%y)*(k%y)%y = y-1 => if any k exists we have one in range [0, y) (if x % y = 0 we don't have any k)naive approach check for all k [0, y), O(y)the better approach is if y is the prime number k = (x / power(y-1, y-2)), O(lgy)
•  » » 2 months ago, # ^ |   +3 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)))
•  » » » 2 months ago, # ^ |   +3 Yes you are right
•  » » » 2 months ago, # ^ |   0 so in shortxk (mod y) = y-1x = ((y-1) * pow(x, phi(y))) % yso either y is prime -> phi(y) = y-2,or there is some phi value for yright?
 » 2 months ago, # |   0 read up on CRT