Volodya333's blog

equation with remainder of the division
By Volodya333, history, 6 years ago, translation, In English

Problem statement: Given n and equation n*x % (x-n) = 0. How many solution. Thank in advance, and sorry for my poor English.

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

»
6 years ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

This solution is wrong the reason is stated in the replies.

I'm not 100% sure about my solution but here you go.

since n*x%(x — n) = 0 then nx — m(x — n) = 0.

nx — mx + mn = 0

moving things around we get

nx = mx — mn => mx — mn = nx turning this into a congruence

equation

we choose x as the mod

we get mx = mn (mod x) => mn = 0 (mod x)

since we know the constant is n then mn — nx = 0

by solving for m we get m = x

by substituting in the first equation we get

nx — x(x — n) = 0

nx — xx + xn = 0

2nx — xx = 0

by solving for n we get n = x/2.

If there is anything wrong please note it out

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    we always have more than 1 answer, for example n = 6, x = 3 and n = 6, x = 4. The number of dividers of the number n is similar to the number of answers, but this is not true

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

      Yes you are right I think the problem is in this line:

      we get mx = mn (mod x) => mn = 0 (mod x)

      since we know the constant is n then mn — nx = 0

      I considered the constant to remain n but since one of the two numbers changed then this is wrong.

      → Reply
»
6 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Just use that n*x % (x-n) = n*(x-n + n) % (x-n) = (n*(x-n) + n^2) % (x-n) = n^2 % (x-n).

So the number of solutions is just the numbers of divisors of n2.

→ Reply