Блог пользователя FeiWuLiuZiao

an easy number theory problem, but don't know how to proof
Автор FeiWuLiuZiao, 8 часов назад, По-английски
$$$ i, j, x, p:\exists k: i+kx\equiv j\pmod p\Leftrightarrow i\equiv j\pmod{\gcd(x,p)} $$$
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 часов назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      6 часов назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        6 часов назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
»
6 часов назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить