# How to show that integers $x_0+\frac{m}{d}t$, $t = 0, 1,…, d-1$, are pairwise incongruent modulo m.(Hint! Antithesis.)?

Let. $m \in N, a, b \in$ Z such that $a \not \equiv 0 \pmod m$ and denote $d= \gcd(a, m)$. Suppose that $x_0 \in$ Z satisfies $ax_0 \equiv \pmod m$ How to show that the integers $x_0+(m/d)t$, $t = 0, 1,..., d-1$, are pairwise incongruent modulo m. (Hint! Antithesis.)

-
Is $syt(a,m)$ supposed to be $\gcd(a,m)$? You’re missing the right-hand side of the congruence involving $ax_0$. –  Brian M. Scott Sep 21 '11 at 9:26
The hint says you should assume two of them are congruent and derive a contradiction. –  anon Sep 21 '11 at 9:45
You can drop the "half a congruence" and it won't change how you'd solve the problem, so I'm guessing you wrote something else wrong. The numbers (m/d)t with t=0,1,...,d-1 are all pairwise incongruent modulo m, with absolute no conditions other than that d is a divisor of m. Adding $x_0$ to each of them won't change that. –  Barry Smith Sep 21 '11 at 10:38

But let's suppose we didn't come at it from that direction. This is meant to be above the level of this question, but the hint above is the important thing. Suppose that we had an m-cycle $\sigma$, an element of the permutation group, whose lowest index was $x_0$. Then consider the cycle decomposition of $\sigma ^a$. One can consider Lagrange's Theorem and cyclic subgroups to arrive at the conclusion that if $a, m$ are relatively prime, then it's still an m-cycle. If not, then it's not. It's a funny parallel, but one nonetheless.