speedster's blog

prove this.
By speedster, history, 11 years ago, In English

How can we prove this : no of unique outputs to (i*j)%k where i can be any number j and k are known is k/__gcd(k,j);

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

»
11 years ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it

You need to find for which a there exists a solution to ij ≡ a (mod k) where i is a variable. Obviously if (k, j) = 1 then j has an inverse mod j so for any a < k there exists an unique solution.

Now suppose (k, j) = d! = 1, then your equation becomes equivalent to finding an l such that ij = lk + a or ij + ( - l)k = a. A pair i, l exists if and only if , so a = dx where x has some random value. Now you have d * x < k so x < k / d, so x can range from 0 to k / d - 1, so there are exactly k / d variables for which there exists a solution.

→ Reply