Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.