[ Pobierz całość w formacie PDF ]
.2.1THE INTEGERS MOD N AND SYMMETRIES37Proposition 2.1 Let Zn be the set of equivalence classes of the integersmod n and a, b, c ∈ Zn.1.Addition and multiplication are commutative:a + b≡ b + a(mod n)ab≡ ba(mod n).2.Addition and multiplication are associative:(a + b) + c≡ a + (b + c)(mod n)(ab)c≡ a(bc)(mod n).3.There are both an additive and a multiplicative identity:a + 0≡ a(mod n)a · 1≡ a(mod n).4.Multiplication distributes over addition:a(b + c) ≡ ab + ac(mod n).5.For every integer a there is an additive inverse −a:a + (−a) ≡ 0(mod n).6.Let a be a nonzero integer.Then gcd(a, n) = 1 if and only if there ex-ists a multiplicative inverse b for a (mod n); that is, a nonzero integerb such thatab ≡ 1(mod n).Proof.We will prove (1) and (6) and leave the remaining properties to beproven in the exercises.(1) Addition and multiplication are commutative modulo n since theremainder of a + b divided by n is the same as the remainder of b + a dividedby n.(6) Suppose that gcd(a, n) = 1.Then there exist integers r and s suchthat ar + ns = 1.Since ns = 1 − ar, ra ≡ 1 (mod n).Letting b be theequivalence class of r, ab ≡ 1 (mod n).Conversely, suppose that there exists a b such that ab ≡ 1 (mod n).Then n divides ab − 1, so there is an integer k such that ab − nk = 1.Letd = gcd(a, n).Since d divides ab − nk, d must also divide 1; hence, d = 1.38CHAPTER 2GROUPSSymmetriesA symmetry of a geometric figure is a rearrangement of the figure preserv-ing the arrangement of its sides and vertices as well as its distances andangles.A map from the plane to itself preserving the symmetry of an objectis called a rigid motion.For example, if we look at the rectangle in Fig-ure 2.1, it is easy to see that a rotation of 180◦ or 360◦ returns a rectangle inthe plane with the same orientation as the original rectangle and the samerelationship among the vertices.A reflection of the rectangle across eitherthe vertical axis or the horizontal axis can also be seen to be a symmetry.However, a 90◦ rotation in either direction cannot be a symmetry unless therectangle is a square.ABABidentity-DCDCABCD180◦-rotationDCBAABBAreflection-verticalaxisDCCDABDCreflection-horizontalaxisDCABFigure 2.1.Rigid motions of a rectangleLet us find the symmetries of the equilateral triangle 4ABC.To find asymmetry of 4ABC, we must first examine the permutations of the verticesA, B, and C and then ask if a permutation extends to a symmetry of thetriangle.Recall that a permutation of a set S is a one-to-one and ontomap π : S → S.The three vertices have 3! = 6 permutations, so the trianglehas at most six symmetries.To see that there are six permutations, observethere are three different possibilities for the first vertex, and two for thesecond, and the remaining vertex is determined by the placement of the2.1THE INTEGERS MOD N AND SYMMETRIES39first two.So we have 3 · 2 · 1 = 3! = 6 different arrangements.To denote thepermutation of the vertices of an equilateral triangle that sends A to B, Bto C, and C to A, we write the arrayA B C.BCANotice that this particular permutation corresponds to the rigid motionof rotating the triangle by 120◦ in a clockwise direction.In fact, everypermutation gives rise to a symmetry of the triangle.All of these symmetriesare shown in Figure 2.2.BBidentityTT-ABCTTid =ABCTTABCAACrotationTT-ABCTTρ1 =BCATTABCCCBrotationTT-ABCTTρ2 =CABTTABCBCAreflectionTT-ABCTTµ1 =ACBTTABCABBreflectionTT-ABCTTµ2 =CBATTABCCAAreflectionTT-ABCTTµ3 =BACTTACBCFigure 2.2.Symmetries of a triangleA natural question to ask is what happens if one motion of the trian-gle 4ABC is followed by another.Which symmetry is µ1ρ1; that is, whathappens when we do the permutation ρ1 and then the permutation µ1? Re-member that we are composing functions here.Although we usually multiply40CHAPTER 2GROUPSTable 2.2.Symmetries of an equilateral triangle◦idρ1ρ2µ1µ2µ3ididρ1ρ2µ1µ2µ3ρ1ρ1ρ2idµ3µ1µ2ρ2ρ2idρ1µ2µ3µ1µ1µ1µ2µ3idρ1ρ2µ2µ2µ3µ1ρ2idρ1µ3µ3µ1µ2ρ1ρ2idleft to right, we compose functions right to left.We have(µ1ρ1)(A) = µ1(ρ1(A)) = µ1(B) = C(µ1ρ1)(B) = µ1(ρ1(B)) = µ1(C) = B(µ1ρ1)(C) = µ1(ρ1(C)) = µ1(A) = A.This is the same symmetry as µ2.Suppose we do these motions in theopposite order, ρ1 then µ1.It is easy to determine that this is the sameas the symmetry µ3; hence, ρ1µ1 6= µ1ρ1.A multiplication table for thesymmetries of an equilateral triangle 4ABC is given in Table 2.1
[ Pobierz całość w formacie PDF ]