An odd numbers has a multiplicative inverse modulo a power of two.
The inverse of 16807 mod 216 is 22039.
That means that (16807 * 22039) % 65536 == 1
, and consequently, that
(16807 * 22039 * x) % 65536 == x
And
k = (22039 * x) % 65536
So you don't have to try anything, you can simply calculate k
directly.