maybesomeone's blog

Math problem
By maybesomeone, history, 2 years ago, In English

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

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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)

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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)))

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yes you are right

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so in short

      xk (mod y) = y-1

      x = ((y-1) * pow(x, phi(y))) % y

      so either y is prime -> phi(y) = y-2,

      or there is some phi value for y

      right?

      → Reply