Question about modular arithmetic

Post Reply New Topic

Hello, all. I've been reading an Algorithms textbook, and there's something I just can't seem to understand, as pertains to the nature of multiplicative groups modulo n.

The text defines modular arithmetic as such, given we have two numbers a and b, and a' and b' such that a=a'(mod n) and b=b'(mod n), then ab = a' * b' (mod n). It then concludes (without any explanation that I can find), that the Multiplicative Group Modulo n is define as Zn = {[a]n which is in Zn: great common denominator of a and n = 1}. In other words, the group Zn is all the numbers 1 to n -1 that are relatively prime to n. My question then, is why is this? Addition has no such restraint. I've tried to find an example illustrating this, but I can't. For example, let's take Z15*, and take two numbers that are not relatively prime to 15, 18 and 21 (as three 3 and 5 divide 15 and 3 divides 21). So, my calculation by the definition is as follows:

a = 18 = 3 (modulo 15) = a'
and b = 21 = 6 (modulo 15) = b'

Thus we have a*b = 18 * 21 = 378 = 3 (modulo 15), and
a' * b' = 3 * 18 = 18 = 3 (modulo 15).

So, why aren't 18 and 21 (or there smallest positive elements in their respective equivalence classes, 3 and 6), not defined for the Z15 multiplicative group?

Thanks.

If you are asking why the Z15* does not contain say 18, consider
18 = 3 mod 15.

For Z15*U{3} to be a group, 3 must have a multiplicative inverse mod 15. Hence we need
3x = 1 mod 15
=>
need a solution to the diphantine equation: 3x - 15y = 1
Somewhere as a preliminary you should know that the GCD of (3,15) is also the minimum positive integer that is a linear combination of 3 and 15, so if 3x - 15y = 1 has an integral solution (15,3) would be relatively prime.

That is, there exists x such that xa = ax = 1 mod(n) iff (n,a) are relatively prime. Therefore, the group can only have multiplicative inverses if all the numbers are relatively prime to 15.

That what you wanted?

I think I'm starting to understand now, you're saying that the the multiplicative group modulo n must have existing multiplicative inverses defined, otherwise it doesn't constitute a finite group, right?

Precisely, as per the definition of a group.

If the definition it gave you is as listed I can see how this might be less than apparent. The proper definition of modular congruence is
a = b (mod n) iff n | (a-b), i.e. n divides (a-b)

and we can derive various other properties from this.

Yeah, the stupid textbook doesn't point that out at all. Thanks again.

Z modulo N(the integers modulo n(any positive integer) is a collection of Unital Rings. If n=prime, than Z modulo n forms a
Field.