1
$\begingroup$

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.)

  • 0
    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.2011-09-21

1 Answers 1

1

This is one of those funny times when you can go in a weird way about this question.

First, the right way. Assume that two are equal. Your goal is to find a contradiction. You should do this by taking their difference and paying close attention to what divides it. Voila.

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.

I hope my sidetracking didn't go too far afield.