MDantas's blog

Theory Number Problem
By MDantas, 12 years ago, In English

Given four integers N,M,x,y ( 1 <= x,y,N,M <= 10^9 ), what's the minimum value of T such that:

T ≡ x mod N

T ≡ y mod M

Can somebody help me?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Please use the Chinese Remainder Theorem.

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

    How can I use Chinese Remainder Theorem when N,M aren't coprimes ?

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

      You can calculate D = GCD(N, M) and the remainders modulo D, N / D, M / D, and then you'll just need to solve the resulting congruence (if x mod D != y mod D, then, obviously, there is no solution).

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

        T*(d^-1) ≡ x/d mod N/d

        T*(d^-1) ≡ y/d mod M/d

        This way ?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 3   Vote: I like it +10 Vote: I do not like it

          Just T ≡ (x % D) mod D, T ≡ (y % D) mod D, T ≡ (x % (N / D)) mod (N / D), T ≡ (y % (M / D)) mod (M / D)

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

T=N*k+x, T=M*p+y => N*k+x=M*p+y <=> N*k-M*p=y-x. Now it's Extended Euclid's algorithm problem. Use it to find k and p.

→ Reply