When I multiply the set

$$\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$$

by $2$ and take the remainder mod $10$, I get the following repeated pattern.

$$\{2, 4, 6, 8, 0, 2, 4, 6, 8\}$$

Multiplication by any even number creates a similar effect (e.g. multiplication by $4$ is $\{4, 8, 2, 6, 0, 4, 8, 2, 6\}$). But multiplication by odd numbers instead creates a permutation of the elements.

$$ \times 3 = \{3, 6, 9, 2, 5, 8, 1, 4, 7\}\\ \times 9 = \{9, 8, 7, 6, 5, 4, 3, 2, 1\}\\ $$

even when the number is not prime. My question is: why? It clearly has to do with the fact that $2$ and $5$ are the prime factors of $10$, but I'm not sure how. Specifically, I'm wondering:

  • Why does multiplication by $k \pmod{n}$ fail to be injective when $\gcd(k, n) \ne 1$?
  • Why does multiplying by $2$ split the integers mod $10$ into two identical groups?
  • In the case when multiplication by $n$ is injective, is there any way to relate $n$ to the permutation caused by multiplying by it?

I know this is related to group theory, but don't know group theory, so I would appreciate learning the names of the concepts on display here as well.


To add some informality beside the answer @CPM has given, it is about the factor being coprime to 10. If the factor is coprime, it can't coincide to its starting point until $\text{lcm} (factor, 10)$. If you lay it out on a number line without doing the modulus it will be more clear. Here's one for the case of $\times 3$:

number line

3 and 10 are coprime, so after $0$, they will not coincide until 3*10 = 30. You can fit ten 3's in that space, meaning you will touch every number. Similarly, $\text{lcm}(2,10)$ is 10, so it will just repeat after it reaches 10, touching only 5 numbers. A couple terms you might be interested here are 'subgroup' and 'generator'. They don't quite apply in this case but they might match the concepts you are thinking of.

For relating a permutation to the element, you can just say trivially that e.g. $\times 9$ is the permutation (1->9, 2->8, 3->7, ...), a.k.a. $\text{p}_9(x) = 9*x \ (mod \ 10)$. Since this is technically not a group it doesn't cleanly map to a set of permutations. $\times 2$ for example isn't a proper permutation because 2->4 but also 7->4. As you note, this scenario is avoided if the modulus has prime size.

One thing I've had fun with is representing sets and operations as dots and arrows (formal Cayley graphs are an example). If you do this you can get clearer insight into the relation between permutations and the underlying set, regardless of whether it's a formal group or not. (By the way I'm learning group theory myself right now. A Book of Abstract Algebra. Great book, finally a group theory book easy enough for me >.<).

Mathematica code for the number line above:

Graphics[{Red, PointSize[Medium], Point[Thread[{3 Range[0, 10], 0}]]},
 Ticks -> {5 Range[0, 6]}, PlotRange -> {{0, 30}, {-1, 1}}, Axes -> {True, False}]

Great question and you are right, it does have much to do with group theory. When $gcd(a,n)=1$, there are numbers $s, t$ such that $as+nt=1$ (you can find these by using the Euclidean Algorithm). But when you reduce this equation mod $n$, you see that $a*s=1$ (mod $n$). This means when you multiply every number in that set by $a$, this map is invertible. Namely by the map you get by multiplying by $s$. This is why it is injective as you observed.

I guess I should add a bit more about your other questions. If $gcd(a,n)=d>1$, then you see why this multiplication map is not injective. Since clearly $a*0=0 (mod n)$, but also if $d$ is a common divisor, say $ds=a$ and $dt=n$. Then $a*t=(ds)t=sn=0$ mod $n$. So $t$ also gets mapped to $0$ showing it isn't injective. This is what is called a zero-divisor in ring theory.

The others you will certainly learn more about when you take an abstract algebra course, but I think it will be more fun for you to play around with those very questions! You are on the verge of observing some very important results that generalize to groups :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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