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);
# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | orzdevinwang | 3570 |
4 | Geothermal | 3569 |
4 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3531 |
8 | Radewoosh | 3521 |
9 | Um_nik | 3482 |
10 | jiangly | 3468 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 162 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 151 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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);
Name |
---|
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.