グラフ理論の問い（続く）

I am still confused by the solution statement to problem 75 in The Art of Computer Programming v4 fascicle 2. As indicated below, even knowing
1. t = 0 mod m where m is number of columns is torus
2. t+d = 0 mod n where n is number of rows in torus
3. t+k is relatively prime to c (from problem 74).
I do not see how (d-k)m/d is relatively prime to kn/d.

Then, even given this, I do not see how the number of Hamiltonian cycles depends on SUM over k:d CHOOSE k. Would there be only one Hamiltonian cycle in the graph for each k, or for each k, is the number of Hamiltonian cycles the number of ways to select k items from d?
1. What is the role of k in determining a Hamiltonian cycle? Cross-reference problem 74.
2. Given that the gcd((d-k)m, kn)=d, why do we know we can have this number? i.e. as a Hamiltonian cycle occurs iff t+k rel. prime to c, how does the gcd equality above relate to this relative prime relationship?