Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

FeiWuLiuZiao's blog

an easy number theory problem, but don't know how to proof
By FeiWuLiuZiao, 4 hours ago, In English
$$$ i, j, x, p:\exists k: i+kx\equiv j\pmod p\Leftrightarrow i\equiv j\pmod{\gcd(x,p)} $$$
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

First of all, since gcd(x, p) divides p, we have i+kx == j (mod gcd(x, p)). What is i+kx (mod gcd(x, p))? kx is divisible by gcd(x, p), so i+kx becomes just i. We got i == j (mod gcd(x, p)).

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

    But how you are so sure that if I+kx is congruent to j in mod p, the same congruency will be followed in mod gcd(x,p)?

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

      Hi! Consider this: let us have two numbers a, b that are congruent modulo p (a == b (mod p)). Then, a + kp = b. Now let's take both sides modulo some number q, which is a divisor of p. We get a+kp == b (mod q); here, kp is just 0 modulo q, so a == b (mod q). We conclude that, in general, if two numbers are congruent modulo p, they are also congruent modulo any divisor of p (including gcd(p, x)).

      → Reply
      • »
        »
        »
        »
        91 minute(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ur prooving $$$\Rightarrow$$$ not $$$\Leftrightarrow$$$

        → Reply
»
117 minutes ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

i + kx = pn + j (let say where n is any integer) => i = j + (pn — kx) Now, we know gcd(x, p) can be written as ax + bp (here , a = -k and b = n).

→ Reply