pokeland157's blog

Need help in a problem
By pokeland157, history, 4 weeks ago, In English

Link : Problem

Can someone please explain(in simple words) why we need to take only numbers that are coprime with n, I read the editorial but still can't fully understand the proof that why a non coprime number will give prod%n != 1

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Consider a number x such that gcd(x, n) = L > 1.

Suppose that there exists an integer k such that

kx ≡ 1 (mod n)

kx $$$-$$$ 1 ≡ 0 (mod n)

Then there exists an integer d such that:

kx $$$-$$$ 1 = nd (since kx $$$-$$$ 1 is divisible by n)

We obtain that:

kx $$$-$$$ nd = 1

That is, it is a Diophantine equation of the form kx + ($$$-$$$ d) * n = 1

That is, we have reduced it to the form:

ax + bn = c, where a = k; b = $$$-$$$ d; c = 1.

It is known that if c is not divisible by gcd(x; n), then such an equation has no solutions. In our case gcd(x, n) = L > 1 => 1 is not divisible by L, whence c is not divisible by gdc(x; n)

Contradiction.

Proof of the fact above and information about Diophantine equation you can find here:

Emaxx: http://e-maxx.ru/algo/diofant_2_equation (on russian)

Translated Emaxx: https://cp-algorithms.com/algebra/linear-diophantine-equation.html (on english)

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

    just out of curiosity, Do you have any link or proof that shows:

    It is known that if c is not divisible by gcd(x; n), then such an equation has no solutions. In our case gcd(x, n) = L > 1 => 1 is not divisible by L, whence c is not divisible by gdc(x; n)

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Yes, of course. I've updated the post above. There are now links

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

      Let's denote k as gcd(x , n). The equation ax + bn = c can also be written as k * (a * x / k + b * n / k) = c. Which means that k and (a * x / k + b * n / k) are pair divisors of c. In other words, k divides c.

      → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

We can use the fact that: (a * n) % (a * m) = a * (n % m).

Demonstration

Let's name the product that we have to find with P. Then, we have P % n = 1. Using the above observation, it means that there exists k, a common divisor for P and n, for which he have P % n = k * ((P / k) % (n / k)) = 1. Which means the biggest k must be 1. In other words, the greatest common divisor for P and n is 1 (gcd(P , n) = 1). This also means that the numbers we choose to be a part of P must be coprime with n (else gcd(P , n) would be bigger).

→ Reply