Multiplicative group of integers
SummaryAlthough does not generally form a group under multiplcation, —i.e., only those coprime with —does. This group is called the multiplicative group of integers mod and is denoted .
IdeaGenerally we know that the structure —that is, integers modulo under addition—forms a group. What about , the integers modulo under multiplication? No: inverses will be lacking for as well as every element sharing a factor with pf. Perhaps, then, if we take only the subset of consisting of elements coprime with , we would get a group?
Fix , . Want to show that it’s contradictory for to be coprime with and yet not have an inverse (mod ). This entails that is coprime with iff it has an inverse (mod ). Assume and are not coprime. Then exists some with and . Also assume that has an inverse (mod ); that is, that exists some with . By definition of , this means that there is some where . Then we have: Since both terms in the left-hand side product are integral, and since their product is one, then they must both be one. However, by assumption, . Contradiction.As it turns out, this works! Proof below.
ProofFix . Let denote the set of integers coprime with , all taken modulo . We claim that forms a group under multiplication:
1. Closure: given in that is also in pf.
Intuition. The product of two integers coprime with is still coprime with , and that holds in modular systems as well. Proof. Take . Let be the unique representatives of that lie within . Since then are coprime with , and thus so is pf. Since is coprime with , then is, as well pf. Since is coprime with , and since , we have that . Finally, by rules of modular arithmetic, ; thus, .2. Associativity: pf. we have pf.
Prop. If are coprime with , then is coprime with . Proof. Take . Assume for contradiction that is not coprime with . Then exists some dividing both and . Since divides , then it must divide either or , which makes either or share a factor with ; contradiction.
This follows from the fact that .4. Inverses: given any exists a such that pf.