B ( ) :

Transcription

1 B ( ) :

2 2 B.

3 (domain) (commutative ring) (field) R R Möbius Euclid

4 4 B (UFD) (PID) UFD (Abelian sandpile model) ( ) R R

5 . P = {, 2,... }, N = {,, 2,... }, Z = { 2,,,, 2,... }, Q, R, C ( ) S (binary operation) S S S, (x, y) x y (i) (x y) z = x (y z) ( associative law) S (semigroup). x y xy...2. P ( ) S S S, (S-i) x, y S x, y S ) S S (subsemigroup)...4. S = (P, +) S = (N, +)...5. ( ) S, S f : S S, (H-i) f(x y) = f(x) f(y) ( x, y S) f (semigroup homomorphism)...6. S = S = (P, +) f : P P, x 2x...7. S, S f : S S, Im f S ( ) M M S, (ii) M x = x M = x ( x M) M M (identity unit).,, M (monoid).... N + monoid.. P monoid..... S, S S (ii ) S x = x ( x S) 5

6 6 B, S (left identity)., S S (ii ) x S = x ( x M), S (right identity). S, S S S = S.,...2. ( ) M M M, (S-i) M M (S-ii) M M M M (submonoid)...3. Z + Q...4. Q = Q \ {} R = R \ {}...5. ( ) M, M f : M M, (H-i) f (H-ii) f( M ) = M f (homomorphism)...6. M, M f : M M, Im f M ( ) G, (iii) x G y G x y = y x = G, G (group)., y x (inverse), x...9. Q = Q \ {}, R = R \ {}, C = C \ {}...2. M, x M (ii ) y x = M, y x (left inverse)., M M (ii ) x z = M, z x (right inverse). x y z y = z., x G x...2. ( ) G G G (S-i) G G. (S-iii) x G x G., G G (subgroup) (S-i) (S-iii) (S-ii).

7 *** B ( ) *** ( ) G, G f : G G, f(x ) = f(x) ( x S).,, f (group homomorphism) G, G f : G G, Im f G ( ) A, (iv) x y = y x ( commutative law), A (Abelian group).,, + x + y (additive group)., x x Z ( ) R, 2 R R R, (x, y) x + y, (x, y) x y, () + R. (2) R \ {}. (3). (3l) x (y + z) = x y + z z (3r) (x + y) z = x z + y z (left distributive law) (right distributive law), R (ring). (2) (2 ) R \ {} monoid., R (unitary ring) (ring with unity) ( ) R,. ) x x = x =. 2) =. 3) a = ( )a 4) ( a)( b) = ab., ( ) R, R, f : R R (H) + f. (H2) f., 88,.,, 92,.

8 8 B, f (homomorphism as ring)., R, R, f (H2) (H2 ) f., f (homomorphism as unitary ring)., f, (injective homomorphism), f, (surjective homomorphism), f, (R-isomorphism)., f : M M (automorphism) ( ) R, R R (S) + R R. (S2) R R., R R (subring)., R, R (S2) (S2 ) R R., f (unitary subring) R, R (resp. ) f : R R (resp. ), Im f R (resp. ) (domain).2.8. ( ) R, x R, y R xy =, x. y R yx =, x. R, (4) x, y R x y x = y =., R (domain) D, (integral doman)..2.. Z R = Z[ ] = Z + Z = {x + y x, y Z}..2.3 (commutative ring).2.2. ( ) R, (2 ) R., R (skew field) ( ) R, (iv) x y = y x ( commutative law), (commutative ring with unit),, (commutative ring)

9 *** B ( ) *** (field).2.4. F, (field) Q, R, C Z H = {x + yi + jz + kw x, y, z, w R}. i 2 = j 2 = k 2 =, ij = k, jk = i, ki = j, ji = k, kj = i, ik = j..2.7., i), ii), iii), iv),. i) ii), iii). iv).,.

10

11 2 2. R- 2.. R ( R- ) R, M, R M R M M, (a, x) ax () a, b R, x M a(x + y) = ax + ay (2) a, b R, x M (a + b)x = ax + bx (3) a, b R, x M (ab)x = a(bx), M R- (left R-module)., R, (4) x M x = x M R-, x M R x = M., R x M ( R )x = x M (additive group), R = Z M R M M x M nx = x + x + + x }{{} n times,, () (2) (3)., Z () (2) (3) (4) ( R- ) R, M, R M M R M, (x, a) ax ( ) a, b R, x M (x + y)a = xa + ya (2 ) a, b R, x M x(a + b) = xa + xb (3 ) a, b R, x M x(ab) = (xa)b, M R- (right R-module)., R, (4 ) x M x = x ( ) R, S (, ), M R- S-, (5) a R, b S, x M (ax)b = a(xb), M (R, S)- ((R, S)-bimodule) ,, R, M R-. R-,, R- R-. R-,, R-.,.

12 2 B M R-,, R R M a R x M xa := ax M R-., M (R, R)-., R,, (R, R)-., R R- R (vector space).,, , 2..5 ( ) (2 ) (3 ) (4 )., (R, R)-, 2..6 (5) (R- ) R ( ), M R-, N M (i) N M (addtive group ) (ii) a R x N ax N, N M R- (R-submodule). = {} M, M R-, (trivial) R-. R- (non-trivial) R-., R R- (subspace) R ( ), M R-, N M R- (i ) x, y N x + y N (ii) a R x N ax N R, S ( ), M (R, S)-, N M R- S- N M (R, S)- ((R, S)-sub-bimodule) ( ) R ( ), M, M R-, f : M M (I) f (addtive group) (II) a R x M f(ax) = af(x), f R- (homomorphism as left R-module) R- (R-homomorphism)., f, R- (injective R-homomorphism), f, R- (surjective R- homomorphism), f, R- (R-isomorphism)., R- f : M M R- (R-automorphism)., R, R- R- (R-linear map) R ( ), M, M R-, f : M M R- (I ) x, y M f(x + y) = f(x) + f(y) 2 N M (i ) x, y N x y N.. 2 f (I ) x, y M f(x y) = f(x) f(y)..

13 *** B ( ) *** 3 (II) a R x M f(ax) = af(x) R ( ), M, M R-, f : M M R-. N M R- N M R-,. ) f(n) M R-. 2) f (N ) M R-., Im f = f(m) M R-, Ker f = f () M R ( ) R ( ), M = {M i } i I R-, f i : M i M i+ R- fi 2 M i f i Mi f i Mi+ f i+ (III) Im f i = Ker f i+ i I, {f i } (exact sequence) R ( ), M, M R-, f, g, h R-. ) f M exact f. 2) M f exact f. 3) f M g M h exact g ( ). R ( ), M R-, N M R-. M x y y x N,, x M [x] := x + N := {y M y x} = {x + y y N}. M/N = {x + N x M}., a R M/N a(x + N) := ax + N, M/N R-., π : M M/N x M π(x) = x + N π R-.. ), 2) x M [x] = x + N, 3) a R M/N a(x + N) = ax + N well-defined ( ), 4) M/N R-, 5) π : x x + N, ( ) R ( ), M R-, N M R-, M/N R- (quotient R-module), π : M M/N.

14 4 B ( ) R ( ), M, N R-, f : M N R-. M/ Ker f N , Ker f = f () M R-., f : M/ Ker f N f(x + Ker f) = f(x),., ) f well-defined, 2) f, 3) f. ) x y Ker f f(x) = f(y). 2) f(x) = f(y) x y Ker f x + Ker f = y + Ker f. 3) R ( ), M λ (λ Λ) R- (family), M λ R ( ) R ( ), M R-, S M, S M R- (intersection) S R-., R- r i s i i (r i R, s i S), RS. RS S R- (R-submodule generated by S) ( ) R ( ), M R-, S M = RS, M (finitely generated). λ Λ

15 3 3., R., R R a, x R ax R, R R-. R-., R (R, R) ( ) R ( ) R I, R-, I R (left ideal)., I, ) 2). ) x, y I x + y I 2) a R, x I ax I. (right ideal). I, I R (two-sided ideal). (ideal)., ( ) = {} R R m Z, R = Z I = mz = {mx x Z}.., ) 2). x, y Z mx + my = m(x + y) mz, a, x Z a(mx) = m(ax) mz., R = M 2 (R) = {( x z ) } y x, y, z, w R w R. 2 (resp. 2 ) I (resp. J), I (resp. J) R (resp. ).. 2 {( ) } x I = x, z R z 5

16 6 B. ). 2) ( a c ) ( ) ( ) b x ax + bz = d z cx + dz I λ (λ Λ) (resp., ) (family), I λ (resp., ) ), x, y I λ, λ Λ, x, y I λ λ Λ λ Λ x + y λ Λ I λ. 2) ( ) ( ) R S, S (resp., ) Λ L (S) (resp. Λ R (S), Λ(S)), Λ L (S) (resp. Λ R (S), Λ(S)) (S) L = I (resp. (S) R = I, (S) = I ) I Λ L(S) I Λ R(S) I Λ(S) S (resp., )., S = {a,..., a s }, ({a,..., a s }) L (a,..., a s ) L., s =, (a) L (resp. (a) R (a)) (pricipal left ideal) (resp. (pricipal right ideal), (pricipal ideal)) ( ) R,, (Pricipal Ideal Domain) Z.. I Z I. I x > a. x I, x < x x >. x = aq + r q r < a. r r = x aq I, a., x = aq I = (a). { k } 3... (S) L = r i a i r i R, a i S, k N. i= { k }. I = (S) L, J = r i a i r i R, a i S, k N, a i S I i= k r i a i I J I. J. i= 3... ( ). ( ) R (resp., ) I λ (λ Λ) ( ) ( ) ( ) I λ (resp. I λ I λ ) λ Λ L λ Λ R λ Λ λ Λ I λ

17 *** B ( ) *** Z + 6Z = 2Z. a, b Z d, az + bz = dz.. Z az + bz = cz c Z. c az + bz c = ax + by x, y Z. d ax + by = c. a, b cz, c a, b., c a, b c d R, R ( ), f : R R, () f S R f(s) R. (2) f I R (resp., ) f(i) R (resp., ). (3) S R f (S) R. (4) I R (resp., ) I = f ( ) R (resp., )., Ker f = f () R I R. x, y R y x I, x y (mod I), x y I., R = Z, I = mz x y (mod m), x y m I, I,. ) x y (mod I) x 2 y 2 (mod I) x + x 2 y + y 2 (mod I) 2) x y (mod I) x 2 y 2 (mod I) x x 2 y y 2 (mod I) m, n 2, a, b, x a (mod m), x b (mod n) x mn. 3. ( ) m, n, u, v mu + nv =., mu (mod n), nv (mod m) x anv + bmu (mod mn), x. y x x y. 2 m n 3 x y x y (mod mn). 4.

18 8 B ( ) y, x y x y (mod m), x y (mod n)., x y m n. m n, x y m n mn. x y (mod mn), x y mn ( 5 ) a, a 2,..., a k k m, m 2,..., m k, x a (mod m ), x a 2 (mod m 2 ),. x a k (mod m k ) x m m 2 m k.. 8, m, m 2,..., m k. ( ) m, m 2,..., m k, M = m m 2...m k, M = m M = m 2 M 2 = = m k M k, m i M i, 3..8, i =, 2,, k, M i t i (mod m i ), t i., x a M t + a 2 M 2 t a k M k t k (mod M)., x m a, 2 k M 2 M k m, x m a. i = 2, 3,..., k,. y, x y x a i (mod m i ) x y (mod m ), x y (mod m 2 ),. x y (mod m k )., x y m, m 2,..., m k. m, m 2,..., m k, x y M., x y M. x y (mod M) 5 3 5

19 *** B ( ) *** , (= 3 5) n , ( ) R, T R, R f : R R. ) f. 2) f(t ) R. 3) R x x = f(a)(f(b)) (a R, b T )., ( R, f ), ( R 2, f 2 ) ) 2) 3), φ : R R 2 f 2 = φ f.. 3.2, R ( ) R, a R, ba = b a (left inverse), ac = c a (right inverse). a b c, b = c, a (inverse), a (unit). R R,,, R (group of units) ( ) R λ (λ Λ) ( ), R = λ Λ R λ (x λ ) λ Λ + (y λ ) λ Λ = (x λ + y λ ) λ Λ (x λ ) λ Λ (y λ ) λ Λ = (x λ y λ ) λ Λ, R ( ). R λ (λ Λ) (direct product),., λ Λ, λ π λ : R R λ, (x λ ) λ Λ x λ R = R λ π λ λ Λ S f λ : S R λ λ Λ, f : S R λ Λ π λ f = f λ. R

20 2 B Λ, ( ) R λ (λ Λ) ( ), λ Λ R λ R = λ Λ R λ = {(x λ ) λ Λ x λ }, R R λ ( ). R λ (λ Λ) (direct product),., λ Λ λ Λ, λ ι λ : R λ R, x λ (...,,, x λ,,,... ) R = R λ π λ λ Λ S f λ : R λ S λ Λ, f : R S λ Λ f ι λ = f λ. R ( ) R ( ), I R. R x y (mod I) y x I. R, R/I, x R [x] = {y T y x (mod I)}., R/I [x] + [y] = [x + y], [x][y] = [xy],, well-defined, R/I ( ). R I., [x] x + I.. ) 2) well-defined x x 2 (mod I) y y 2 (mod I) x + y x 2 + y 2 (mod I) x y x 2 y 2 (mod I). 3) R/I () + R. (2) R \ {} ( ). (3). (3l) x(y + z) = xy + zz (left distributive law) (3r) (x + y)z = xz + yz (right distributive law)

21 *** B ( ) *** 2. (). (2) ([x][y])[z] = [(xy)z] = [x(yz)] = [x]([y][z]) []. (3) R = Z, m (m) = mz = {mx x Z}. Z/(m) = Z/mZ, Z/(m) = m Z Z/2Z (mod 2) (mod 4) (mod 7). ( ( ) 848 = 47 7 ) 24 (mod 8) (mod 9). 2 ( = 45 9 ) (mod ). 3 (75428 ( ) ( ) = ) (mod 3). 4 ( ( ) 32 = ) ( ) n, n n φ(n), (Euler s totient function). φ(n) (phi function).,. (Z/nZ). φ(n) = (Z/nZ). 3.3.: φ(n) n φ(n) n, n = n n 2 n r, i j n i n j, Z/(n) Z/(n ) Z/(n 2 ) Z/(n r )., (Z/(n)) (Z/(n )) (Z/(n 2 )) (Z/(n r )). 8 2,, 2, 4, 6, 8, , , ( ) , 9. 3, , 3.

22 22 B φ(p e ) = p e (p ).,..., p e p e px (x =, 2,..., p e ) φ(p e ) = p e p e n, n = p e pe2 2 per r ( p i ) n, r ) φ(n) = ( pi n, (Euler )., m = p i= p e i i a φ(m) (mod m) a p (mod p) (Fermat ).. Lagrange ( ) n a ( a < n) a n (mod n) Fermat (Fermat test). 5 a =, 2,..., n, a a n (mod n). n (pseudoprime) n a, (a, n) = a n (mod n), n Carmichael (a, n) a n (mod n) (Korselt s criterion) n.. 7 () n Carmichael (2) n (square-free), p n p (p ) (n ). 5 Fermat O(log n),. 6 quantum computer,.,. (Shor s factorization), test#article chapter

23 *** B ( ) *** n N. φ(d) = n d n. d d n. n n n/d, n/d x (x =, 2,..., d) x d, φ(d). d n, φ(d) = n d n n = 2 φ() + φ(2) + φ(3) + φ(4) + φ(6) + φ(2) = = G, d x d = x G d G.. D = n. d d n, d ψ(d)., d a,, a, a 2,..., a d, x d =, d a k, (k, d) =,., φ(d),, d ψ(d) = φ(d), ψ(d) =. ψ(d) φ(d). Langrange, n n = ψ(d) φ(d) = n d n d n, ψ(d) = φ(d)., ψ(n) = φ(n) > n ( ) ζ(s), s = x + iy (Re s = x > ), ζ(s) = n= n s = s + 2 s + 3 s + s = x+iy (x > ), n s = n x+iy = n x n iy = n x e iy log n = n x (cos(y log n)+ i sin(y log n)) /n s = /n x. n s = n x, x >,. x. 8 n= n= ζ(s) = p : p s = ( ) ( ) ( ) 2 s 3 s 5 s. 9 ( ) ( ) ( ). 8 (Riemann hypothesis),,. ζ(s) s /2.,. 9 x = + x + x2 +.

24 24 B ( n ) n N n n (nth primitiveroot of unity). ζ n = cos 2π n + i sin 2π n, ζ k n ( k n, k n ) n, φ(n). ζ n ζ n = n = 3 ω = + i 3, ω 2 = i 3 2 2, n = 4 ±i ( ) n N Φ n (X) = ( ) X ζ k n k:(k,n)=, (cyclotomic polynomial). Φ n (X) = X n. deg Φ n (X) = φ(n) n Φ (X) = X Φ 2 (X) = X + Φ 3 (X) = X 2 + X + Φ 4 (X) = X 2 + Φ 5 (X) = X 4 + X 3 + X 2 + X + Φ 6 (X) = X 2 X +. d n Möbius (Möbius ) n n N µ(n). µ() =, n >, n = r i= pei i ( ) r e = = e r =, µ(n) = otherwise. µ(n) n Möbius : µ(n) n µ(n) 2.

25 *** B ( ) *** n Z, n >. µ(d) = d n. n n = p e per r (r ) µ (d) = d n µ (p x px r x e,..., x r e r, x + + x r = x n = 2. r ) = x,..., x r ( ) x + +x r = µ() + µ(2) + µ(3) + µ(4) + µ(6) + µ(2) = = r ( ) r ( ) r = ( ) r = x x= ( ). f N, n N f(d) = g(n) d n d n ( n ) µ g(d) = f(n) d. ( n ) µ g(d) = ( n ) µ f(d ) = d d d n d n d d d d n ( n ) µ f(d ) = f(d ) µ(t) d d n t n d,, n N. a =, µ(t) = a >. t a d n ( n ) µ d = φ(n) d n = 2. µ(2) + µ(6) 2 + µ(4) 3 + µ(3) 4 + µ(2) 6 + µ() 2 = = ( 2). f N, n N f(d) = g(n) d n g(d) µ( n d ) = f(n) d n

26 26 B Φ n (X) = d n(x d ) µ( n d ) n = 2, 2 {, 2, 3, 4, 6, 2}, µ() = µ(6) =, µ(2) = µ(3) =, mu(4) = µ(2) = Φ 2 (X) = (X ) µ(2) (X 2 ) µ(6) (X 3 ) µ(4) (X 4 ) µ(3) (X 6 ) µ(2) (X 2 ) µ() = (X2 )(X 2 ) (X 4 )(X 6 ) = X4 X Euclid (Euclid ) a, b Z, ax + by = d x, y Z (d = (a, b)). < a < b. b = r, a = r, b a q, r 2 b = aq + r 2. r 2,, r i = r i q i + r i+ (i =, 2,..., n) r n, r n+ = d = r n r n = r n 2 q n r n = r n 2 q n (r n 3 q n 2 r n 2 ) = ( + q n q n 2 )r n 2 q n r n 3 = ( + q n q n 2 )(r n 4 q n 3 r n 3 ) q n r n 3 = ( + q n q n 2 )r n 4 (q n + q n q n 2 q n 3 )r n 3 = r n = ax + by x, y x + 6y = x, y Z.. Euclid, 6 9 = = = 3 2 = 2 (9, 6) = 6 = = = = 7 (9 7 ) 3 = 7 ( + 3) 9 3 = (6 9 )( + 3) 9 3 = 6 ( + 3) 9 ( ) =

27 *** B ( ) *** x (mod 9), x (mod 6) x, y Z.. Euclid, 6 9 = = = 3 2 = 2 (9, 6) = 6 = = = = 7 (9 7 ) 3 = 7 ( + 3) 9 3 = (6 9 )( + 3) 9 3 = 6 ( + 3) 9 ( ) = Z/nZ (Z/nZ) ( ), (Z/p e Z) i) p, (Z/p e Z), p e (p ). 2 ii) p = 2, e =, 2, e 3, (Z/2 e Z) Z/2Z Z/2 e 2 Z (mod 44) x (mod 44) x. 44 = Z/44Z Z/2 4 Z Z/3 2 Z. 7 2 = 49 (mod 2 4 ) 55 7 (mod 2 4 ), 55 (mod 3 2 ) 55 (7, ) ( Z/2 4 Z ) ( Z/3 2 Z ) (Z/44Z) ( , ) (7, ) 55, (Z/5Z) 5 = 4, ( Z/5 2 Z ) ( 5 (5 ) = 2, Z/5 3 Z ) 5 2 (5 ) =. 22 ( Z/2 2 Z ) ( 2, Z/2 3 Z ) ( Z/2Z Z/2Z, Z/2 4 Z ) Z/2Z Z/4Z. 23 ( ) ( ) 6.html

28 28 B (mod ) (mod ), 3 4 ( ) 2 (mod ) ( 3 4 ) ( ) 3 3 Z/Z. (,.) 3 (Z/Z), (Z/Z) = {, 3, 7, 9} = (mod ) (mod 2) (mod 2), (mod 2), n 8 2n 4 (mod 2), 8 2n+ 8 (mod 2)., 8 2 (8, 2) = 4, 8 Z/2Z,, 8 n = 2 2 3, f : Z/3Z Z/2Z, x 4x. f(2) = 8, (Z/3Z) 2, 8 2 f ( 2 2) f() 4 (mod 2) a m n. 26 a Z/nZ. () a n a Z/nZ, (2). () a Z/nZ, a a n b a b (mod n). b k (mod n) k., m k q, r. a m b kq+r ( b k) q b r b r (mod n) (2) a Z/nZ, (),. a n (a, n) l., n = p e pe r r, l = p f pf r r f i e i ( i r). S = {i; f i = },, m a m Z/nZ = Z/p e Z Z/pee r Z i S Z/p e i i Z., a m Z/nZ m i S φ (p ei i ) = p ei i (p i ) i S. 24 ( 27, - 3) 25 ( 26, - 3) 26,,, mod (mod 49). 49 = 7 2 (Z/49Z) (Z/49Z) , 6 4, , 3, (mod 49). 28 (25, ) = 5, (mod ) = φ(2 2 ) = (mod ), (mod ), (mod ),

29 4 4. R R, R n X,..., X n f(x) = f(x,..., X n ) = a i,...,i n X i X i n i,...,i n R[X,..., X n ], R n. ax i X i n, i + + i n,. f, f(x), deg f. deg = f(x, Y ) = 2 X 3 + X 2 Y + X Y Z[X, Y ] 3, g(x) = X X Q[X] 2., R R f(x), g(x) R[X] deg fg = deg f + deg g R. S R, S R R. S R, [S] R. R R S R, [R S] R [S] R = Z R = C. S = {i}, Z[i] R. R R S R, R [S] = {f(s,..., s n ) n f R [X,..., X n ], s,..., s n S}... R = {f(s,..., s n ) n f R [X,..., X n ], s,..., s n S}. ) R R S R R R. 2) R R R = Z R = C. S = {i}, i 2 = Z[i] = {a + ib a, b Z} Z[i].. 29

30 3 B x = a + bi Z[i] x = a bi. N(x) = xx = a 2 + b 2. x, y Z[i], x q, r Z[i] y = xq + r N(r) 2 N(x).. x = a + ib, y = c + id. u, v Z y x = c + id (a ib)(c + id) = a + ib a 2 + b 2 = ac + bd a 2 + b 2 u 2,. q = u + iv Z[i], r = y xq ( r ( y ) N = N x) x q = ac + bd bc a 2 + iad + b2 a 2 + b 2 ad bc a 2 + b 2 v 2 ( ) 2 ( ) 2 ac + bd ad bc a 2 + b 2 u + a 2 + b 2 v = 2. N(r) 2 N(x). ( r N x) = r x r x = N(r) N(x) R = Z R = C. S = {ω}, ω 2 + ω + =. Z[ω] = {a + ωb a, b Z}

31 (P, ) (partially ordered set, poset), x, y P x y (i) x x ( reflexivity) (ii) x y y x x = y ( anti-symmetry) (iii) x y y z x z ( transtivity) S P a S (upper bound) resp. (lower bound) : x S : x a (resp. x a) a S (maximum element) resp. (minimum element) : a S a S (resp. ) a S (maximal element) resp. (minimul element) : a S x a (resp. x a) x P S = P (resp. ), P (resp. P ),, (resp. ) ( ) P P, P (Zorn ). 5.2 R R, p R,. () R/p (2) a, b p, ab p a p b p (3) R a, b, ab p a p b p (4) R a, b, a p b p ab p p (prime ideal).. () (2) ab p, R/p (a + p)(b + p) = p, R/p a + p = p b + p = p. a p b p. (2) (4) R a, b, a p b p a a \ p, b b \ p. (2) ab p ab p. R. 3

32 32 B (4) (3) (3) () R/p R, m R,. () a, m a R a = m a = R. ( m ) (2) R/m m (maximal ideal). () (2) a + m m a m m (a) + m, m (a) + m = R. r R, m m ra + m =. r + m a + m. (2) () m a R x a \ m. R/m x + m m y R (x + m)(y + m) = + m. a a = R R, S ( S) R (i.e. a, b S ab S), a R s.t. a S =., R I = {b b a b S = }. p p, p.. I. b ι (ι I) I, c = b ι, c ι I, c I. 2,., Zorn, p I. p. b p, c p, bc p p (b) + p, p (c) + p ((b) + p) S, ((c) + p) S, s = r b + p, s 2 = r 2 c + p 2 s, s 2 S, r, r 2 R, p, p 2 p., S s s 2 = r r 2 bc + r bp 2 + r 2 cp + p p 2 p p S = R, a R, a R m.. S = {} R R m.. a = R,. () R (2) R, R R.. a R. a a. f a : R a, x xa R a,. a = R. R R. 2 a c. c S =.

33 *** B ( ) *** R, a, b R b = ac ( c R), a b, b a, a b. a R x R, x = ϵa ϵ, a x, x a. 3 a, a 2,..., a n R (n 2) d a i ( i) x a i ( i) x d d R a, a 2,..., a n.,., d, d a, a 2,..., a n d d. a, a 2,..., a n a, a 2,..., a n. a, a 2,..., a n R a i m ( i) a i x ( i) m x m a, a 2,..., a n., a, x R, (i) x a x = ϵ x = ϵa ( ϵ ) (ii) x a x, x a (iii) (a) (x) R (x) = (a) (x) = R R, a R, x R, x a x = ϵ x = ϵa ( ϵ ), a (irreducible element). p R p ab p a p b, p R R,.. p R, p = ab p ab, p a p b. p a, p = ab a p a p, p. b (p) (UFD) R, R a (a ) a = p p 2 p r, (Unique Factorization Domain) ,., a R a = p p r = q q s 2, r = s, p q,..., p r q r.. r. r =, p = q q s, q q s (p ) q (p )., p q, q 2 q s s =. r >, p p r = q q s q q s (p ),, p q. q = ϵ p (ϵ ) p p r = ϵ p q s p 2 p r = ϵ q 2 q s, r = s, p 2 q 2,..., p r q r. 3 x a a x x a (p)

34 34 B ,. (, ) R = Z[ 5] = {x + y 5 x, y Z}. w = x + y 5 R, w = x y 5, N(w) = ww = x y 2 Z N(w w 2 ) = N(w )N(w 2 ). (i) 2, 3, ± 5 R. (ii) (2) R. (iii) (2, + 5). (iv) R UFD. (6 = 2 3 = ( + 5)( 5) ) (PID) R,, (Principal Integral Domain) ,. (, )., 5.2. p (p) (p) p,, R, p R,. (i) (p) (ii) (p) R.. ( ) a R,., a a = a a (a, a ), a, a,., a, a = a 2 a 2 (a 2, a 2 ), a 2, a 2,, a 2., (a) (a ) (a 2 ) (a 3 ) R. i (a i ). 5 R i (a i ) = (b) b R., i b (a i ), (a i ) = (a i+) = (a i+2) =, R a, b. (i) a b d. (ii) (a, b) = (d).. (i) (ii) (a, b) = (c) c R. c a c b c d., c = ax + by x, y R, d a d b d c. c d. (ii) (i) d = ax + by x, y R. c a, b, c a, c b c d. a, b (d), d a b d X, Y, R = Z[X, Y ] UFD. ( ) I = (X, Y ) R., R PID. 5.

35 *** B ( ) *** R a v(a),, Euclid (Euclidian Domain). () a, b R s.t. a, q, r such that b = aq + r, r = v(r) < v(a) (2) a, b v(a) v(ab) Euclid R.. a R. S = {v(x) x a x } N v(a). a = (a)., x a x = aq + r r = r v(r) < v(a), r = x qa a, v(a) ( ) R, F f : R F. () f (2) F x = f(a)f(b)., (F, f), (F, f ) () (2), φ : F F f = φ f.. F = {(a, b) a, b R, b }, F (a, b) = (c, d) ad = bc. F = F /, F (a, b) + (c, d) = (ad + bc, bd), (a, b)(c, d) = (ac, bd), well-defined, F = ( R, R ), F = ( R, R ). f : R F f(a) = (a, R ) R, F R (field of quotients)., R ( ).

36

37 6, R. deg f f R[X,..., X n ], f = gh, deg g, deg h < f g, h R[X,..., X n ], f (degreewise reducible). f R[X,..., X n ] deg f,, (degreewise irreducible) h(x) = 2 X X X + 2 Z[X], g(x) = X X Q[X] f R[X,..., X n ] f R. f R[X,..., X n ] deg f = Z[X,..., X n ] ± F, f F [X] f F [X],, R, f R[X] R[X]. f(x) = 6(X 2 + X + ) Z[X],, f(x) Z[X] 2, 3, X 2 + X + Z[X]. Q[X] R[X] R. f R[X] f = a + a X + + a m X m = m a i X i (a i R, a m ), m (degree), a m (leading coefficient). a m = (monic) m., f, ia i X i f, f (derivative). i= 6... h(x) = 2 X X X + 2 Z[X] 3, 2 monic, h (X) = 6 X X + 2 Z[X] R R[X], f, g R[X], deg(fg) = deg f + deg g. f = m i= a ix i, g = n j= b jx j fg = m i= n j= a ib j X i+j a m b n R R[X,..., x n ], f, g R[X], deg(fg) = deg f + deg g. R[X,..., x n ] = R[X ][X 2 ] [X n ] R, R[X,..., x n ] { } f(x,..., X n ) R(X,..., X n ) = g(x,..., X n ) f(x,..., X n ), g(x,..., X n ) R[X,..., X n ], g(x,..., X n ). 37 i=

38 38 B R, f, g R[X] g R f = gq + r, r = deg f < deg g q, r R[X]..,. f = m i= a ix i, g = n j= b jx j, deg f < deg g. deg f = deg g,, q, r.. f = gq + r = gq 2 + r 2, deg r, deg r 2 < deg g g(q q 2 ) = r 2 r. q q 2 deg g(q q 2 ) deg g > deg r 2 r. q = q 2, r = r R, f R[X], a R, q(x) R[X]., f(x) = (X a)q(x) + f(a), X a f(x) f(a) =. g(x) = X a f(x) = (X a)q(x) + r. X = a r = f(a) R m, f(x) R[X] m.. m. (i) m =,. (ii) m > 2, m. m, f(x) R[X] a f(x) = (X a)f (X)., f (X) m, m., f(x) m R, f(x) R[X] R a, f(a) = f(x) = f R[X], a R, (X a) k f(x) (X a) k+ f(x), a f(x) k, k f(x) a. 2,, R, a R f(x) R[X] k (k 2), a f (X) k. a R f(x) f(a) = f (a) =.., f(x) = (X a) k g(x), g(a)., f (X) = k(x a) k g(x) + (x a)kg (X) = (X a) k {kg(x) + (X a)g (X)} (X a) k f(x).

39 *** B ( ) *** F F [X] Euclid F F [X] PID F f(x), g(x) F [X],. (i) f(x), g(x). (ii) f(x)u(x) + g(x)v(x) = u(x), v(x) F [X] F p(x) F [X],. (i) p(x) F [X] (ii) p(x) F [X] (iii) (p(x)) F [X] (iv) (p(x)) F [X] 6.3 UFD, R UFD., F R f(x) R[X], f(x) (primitive polynomial) h(x) = 2 X 3 +2 X 2 +2 X+2 Z[X] 2 primitive, k(x) = 6 X 2 +3 X+4 Z[X] primitive p R R p R[X], i.e., f(x), g(x) R[X] p f(x) p g(x) p f(x)g(x).. f(x) = a + a X + + a m X m, g(x) = b + b X + + b n X n (a m, b n ). f(x), g(x) p, a j, b k, f(x)g(x) X j+k c j+k = a j+k b + + a j+ b k + a j b k + a j b k+ + + a b j+k. p a k b k, p, p c j+k p f(x)g(x) (Gauss s Lemma) f(x), g(x) R[X], f(x)g(x).., f(x)g(x), p f(x)g(x) p R p f(x) p g(x), f(x), g(x) f(x) = 2 X X + 3, g(x) = 2 X X + 2 Z[X], f(x)g(x) = 4 x x x x + 6 Z[X] a, b F, b = aϵ R ϵ R, a b, a b. approx

40 4 B R = Z, F = Q, Z = {±}, 2 3 ± 2 3., R = Z[i] (i = ), F = Q[i], Z = {±, ±i}, 2 3 ± 2 3, ± 2 3 i f(x) F [X] f(x) = cg(x) c F g(x) R[X]. c, c = c(f) f(x) (content).. f(x) = a + a X + + a m X m, b, b,..., b m B b b b m f(x) = ( a B + a B X + + a m B ) X m B b b b m, a i B b i R R A R, f(x) = A B (c + c X + + c m X m )., c = A B, f (X) = c + c X + + c m X m, f (X) R[X]., f(x) = cf (X) = c f (X) (f (X), f (X) R[X] ), c = a b, c = a b ab f (X) = a bf (X) R[X]., f (X), f (X) ab a b. ab = a bϵ ϵ R., c = cϵ f (X) = ϵf (X) R = Z, F = Q, g(x) = X X Q[X]. c(g) = 6, primitive k(x) = 6 X X + 4 Z[X], g(x) = c(g) k(x) f F [X], f R[X] c(f) R f R[X], f c(f) f, g F [X], c(fg) = c(f)c(g) f(x), g(x) R[X], g(x), f(x) = g(x)h(x) h(x) F [X] h(x) R[X].. f(x) = g(x)h(x) R c(f) = c(g)c(h) = c(h), 6.3. h(x) R[X] f(x) R[X], f(x) = g(x)h(x) g(x), h(x) F [X] g (X), h (X) R[X]. f(x) = g (X)h (X), deg g = deg g, deg h = deg h. g(x) = c(g)g (X), h(x) = c(h)h (X) (g, h R[X] ) f(x) = c(g)c(h)g (X)h (X), 6.3.4, g (X)h (X), 6.3. c(g)c(h) R.,, g (X) = g (X) R[X], h (X) = c(g)c(h)h (X) R[X] f(x) R[X], R[X] F [X] R R[X] f(x), () f(x) R[X] (2) f R (deg f = ),, f (deg f ).. () (2) f(x) R[X], f(x) = c(f)f (X) (f (X) R[X] ), f(x) c(f)f (X) f(x) c(f) f(x) f (X). f(x) c(f) R, f(x) f (A) c(f). (2) ()

41 *** B ( ) *** R R[X].. f(x) R[X], f(x) = c(f)f (X) (c(f) R, f (X) R[X] ). c(f) R c(f) = p p r., R F F [X], F [X] f (X) = g (X) g s (X) (g i (X) F [X]) , h,..., h s R[X], f (X) = h (X) h s (X), deg g i = deg g i., f c(h ) c(h s ), h i F [X] R[X]., 6.3.4, f(x) = p p r h (X) h s (X) f R R[X,..., X n ].. R[X,..., X n ] = R[X,..., X n ][X n ].

42

43 7, R. 7. R m n M m,n (R)., m = n, n, M n (R). n A M n (R) AB = BA = I n B M n (R), (non-singular), B A, A I = R n GL n (R), R (General Linear Group) n A M n (R) det A R.. AB = I, det A det B = det A R., det A R A Ã., t A A. A = t A det A n P n (i, j), Q n (i; c), R n (i, j; a) M n (R). P n (i, j) = i j i j

44 44 B, c R., a R. Q n (i; c) = R n (i, j; a) = i..... i c i j i a.... j , αδ βγ R,. S n (i, j; α, β, γ, δ) = i j i α... β j γ... δ a R, c R, αδ βγ R, 4 n P n (i, j), Q n (i; c), R n (i, j; a), S n (i, j; α, β, γ, δ) M n (R).. det P n (i, j) =, det Q n (i; c) = c, det R n (i, j; a) =, det S n (i, j; α, β, γ, δ) = αδ βγ, Theorem 7..., P n (i, j) = P n (i, j), Q n (i; c) = Q n (i; c ), R n (i, j; a) = R n (i, j; a), S n (i, j; α, β, γ, δ) = S n (i, j; α, β, γ, δ )., α = (αδ βγ) δ, β = (αδ βγ) β, γ = (αδ βγ) γ, δ = (αδ βγ) α m n A M m,n (R), 3, B A (elementary row operations) (resp. (elementary column operations)).

45 *** B ( ) *** 45 (L) 2 (resp. ). (L2) (resp. ) R c. (L3) (resp. ) R a, (resp. ). (L4) αδ βγ R, i, i α j β j, i γ j δ. (R), (R2), (R3). (R4) αδ βγ R, i, i α j γ j, i β j δ..,, (elementary operations) (L) 2 ( ) 2 ( , 3 ( ) ( ) Z ±. (L2) ( ) ( ) ( ) 2 3 ( )., 2 ( ) ( ) 2 2 ( ) ( ) (L3) 2 2 R ( ) ) ( ) , 2 3 ( ) ( ) i =, j = 2, a = 3, b = 7, c = 2, d = 5 (L4) ( ) ( ) , i =, j = 3, a = 3, b = 7, c = 2, d = 5 (R4) ( ) ( )

46 46 B m n A M m,n (R), 3 (L), (L2), (L3), (L4), P m (i, j), Q m (i; c) (c R ), R m (i, j; a) (a R), S m (i, j; α, β, γ, δ) (α, β, γ, δ R, αδ βγ R )., 3 (R), (R2), (R3), (R4), P n (i, j), Q n (i; c) (c R ), R n (i, j; a) (a R), S n (i, j; α, β, γ, δ) (α, β, γ, δ R, αδ βγ R ).. () B = P m (i, j)a (resp. B = AP n (i, j)), B A i j (resp. i j ). (2) B = Q m (i; c)a (resp. B = AQ n (i; c)), B A i (resp. i ) c. (3) B = R m (i, j; a)a (resp. B = AR n (i, j; a)), B A i j (resp. j i ) c. (4) R. A, B M m,n (R), P GL m (R) Q GL n (R) B = P AQ, A B (equivalent), A B M m,n (R).. 3 () ( ) A A (2) ( ) A B B A (3) ( ) A B B C A C. 7.3 A M m,n (R) m n. k min(m, n), i < < i k m, j < < j k n, A i,..., i k j,..., j k k A i,...,i k j,...,j k., A = A, ( ) 2,4 = 5 4., k = m {i,..., i m } = {,..., m}, A,...,m j,...,j m, A j,...,j m., k = n {i,..., i n } = {,..., n}, A i,...,i n,...,n,. Ai,...,in (Cauchy-Binet formula) m, n m n. A M m,n (R), B M n,m (R). det AB = det A i,...,i m det B i,...,im i < <i m n.. n k= a n kb k k= a kb km..... = n k= a n mkb k k= a mkb km k < <k m n a k a km b k b k m a mk a mkm b km b km m

47 *** B ( ) *** 47. n k a n = kb k k a m= kb km LHS =..... = n k a n = mkb k k a m= mkb km n k = n k m= k,..., k m a kσ() a kσ(m) = b kσ() b kσ(m) m..... k < <k m n σ S m a mkσ() a mkσ(m). = = k < <k m n k < <k m n a k a km sgn σ b kσ() b kσ(m) m..... σ S m a mk a mkm a k a km b k b k m = RHS a mk a mkm b km b kmm m = 2, n = 3. A, B M m,n (R) ( ) b b 2 a a 2 a 3 A =, B = b 2 b 22 a 2 a 22 a 23 b 3 b 32 a k a km b k b km. m.... a mk a mkm ( ) ( ) ( ) ( ) ( ) ( ) a a 2 b b 2 a a 3 b b 2 a 2 a 3 b 2 b 22 det AB = det det + det det + det det a 2 a 22 b 2 b 22 a 2 a 23 b 3 b 32 a 22 a 23 b 3 b R. A M m,n (R). e e 2... B = e r... (7.4.) e i ( i r) e i e i+ ( i < r).. R v valuation. A = O ( ), A,. A O. O A M m,n (R), v(a) = min{v(a ij ) a ij }., v(a) A valuation.,,.

48 48 B (i, j), A B, (, ) b, A (i, j) a ij., v(a) = v(b).... i, j, A i, j B. 2 A (, ) a ( ), A B, (, ) b a, ( )...., (, j) aj = qa (j ), j + ( q) (, j). a j., (, ) ( ) (, ). 3 A valuation a (i.e. v(a ) = v(a)), A a, A B, v(b) < v(a)...., ai a, R a i = qa + r, v(r) < v(a ) (7.4.2) q, r R. A i + ( q) B B (i, ) r, v(b) < v(a). 4 A O valuation a ij (i.e. v(a ij ) = v(a)), A a kl a ij, A B, v(b) < v(a)...., v(a ) = v(a). A a 3. A a. a kl (k, l > ) a., A + l C C (k, ) a k + a kl. a k a, a kl, a k + a kl a., 3, 5 A O, A B, b ij.... v(a) = v(aij ) A a ij. a ij A, B = A. 4 v(b) < v(a) B A. A B, B B, v(c) < v(b) C B.. v(a), A a ij. 6 A O A B (),(2),(3). () b. (2) b i = b j = (i >, j > ). (3) b b ij (i >, j > ). 5 A C, c ij C., C, C ij (,) D. D A, d d ij. 2 D B (), (2). B (3). 7 6 (m, n) a a 2... a n a 2 A =.. A a m valuation v(xy) v(x) v(a ij ) = v(a).

49 *** B ( ) *** 49 b... B =. B. B b. A B, A = 3 3 3,. A,, ( ) ( 3) ( ) ( )

50 5 B,. B = R, A GL n (R) P n (i, j), Q n (i; c) (c R ), R n (i, j, a) (a R).. R, A M n (R), 7.4., P k P AQ Q l = B P,..., P k, Q,..., Q l., P n (i, j), Q n (i; c) (c R ), R n (i, j, a) (a R). det B R, r = n, e,..., e r R. 7.5 R, 2 (greatest common divisor; GCD), GCD (GCD domain). 2, (least common multiple; LCM).. R R R R GCD R GCD R GCD. A M m,n (R) k d k (A). d k (A) = gcd { det A i...i k j...j k i < < i k m, j < < j k n }, k d k (A) = , d (A) = gcd(2, ) =, 2 A = 2 2 det A 2 2 = 3, det A 2 3 = 3, det A 2 23 = 3, det A 3 2 = 3, det A 3 3 = 3 det A 3 23 = 3, det A 23 2 = 3, det A 23 3 = 3, det A = 3 d 2 (A) = 3. det A = d 3 (A) = R GCD. A, B M m,n (R) m n. P M m (R), Q M n (R) B = P AQ, d k (A) d k (B)., k min(m, n). 2 a, b R, d () d a d b (2) c a c b c d, d a, b (greatest common divisor)., l () a l b l (2) a x b x l x l a, b (least common multiple).

51 *** B ( ) *** 5. A = (a ij ), B = (b ij ), P = (p ij ), Q = (q ij ) b ij = m r= s= n p ir a rs q sj. i < < i k m j < < j k n det B i,...,i k j,...,j k Theorem 7.3., det(aq) r,...,r k j,...,j k det B i,...,i k j,...,j k = Theorem 7.3. det B i,...,i k j,...,j k = r < <r k m r < <r k m s < <s k n. d det A r,...,r k s,...,s k d det B i,...,i k j,...,j k. d d. det P i,...,i k r,...,r k det(aq) r,...,r k j,...,j k det P i,...,i k r,...,s k det A r,...,r k s,...,s k det Q s,...,s k j,...,j k. P (AQ), d d., A = P BQ, d d R. A M m,n (R) e e 2... B = e r... (7.5.) ( e i ( i r) e i e i+ ( i < r) )., e,..., e r A,. d k (x) = e e 2 e k. 7.6,, R., e i e i+ ( i < r) (e i ) (e i+ ) ( i < r) R, A M m,n (R). A B M m,n (R),, B A (Smith Normal Form). 3 e e 2... B = e r (7.6.)... e i ( i r) (e i ) (e i+ ) ( i < r). e,..., e r A (elementary divisors), A (rank) R., A M m,n (R),., e,..., e r A,. d k (x) = e e 2 e k. 3 R = Z Smith, Henry J. Stephen (86). On systems of linear indeterminate equations and congruences. Phil. Trans. R. Soc. Lond. 5 ():

52 52 B,,, (L), (L2), (L3), (R), (R2), (R3) (L4), (R4)., 7.4.3, R, A GL n (R) P n (i, j), Q n (i; c) (c R ), R n (i, j, a) (a R), S n (i, j; α, β, γ, δ) (α, β, γ, δ R ) , R. () R A M m,n (R), R (elementary divisor ring). (2) R (, 2) A M,2 (R) ( (2, ) A M 2, (R)), R (Hermite ring). (3) R, 2, (Bézout ring).,. (4) R, (ascending chain condition), n I I k I k I k+ I n = I n+ =, R (Noetherian Ring). (5) R, (descending chain condition), n I I k I k I k+ I n = I n+ =, R (Artinian ring). (6) R,, (a) = (b) u R b = au, R (associate ring) R Bézout R Bézout GCD R GCD domain R R R Bézout R. () R R Bézout. (2) R R Bézout. (3) R (i), (ii) :

53 *** B ( ) *** 53 (i) R Bézout (ii) a, b, c R (a, b, c) = R p, q R (pa, pb + qc) = R. (4) R, A M m,n (R) B.. () [2, p.465] R, 2, a, b R, d R αδ βγ R α, β, γ, δ R ( ) ( ) α β a b = γ δ ( ) d. d = aα + bγ (a) + (b) (d) (a) + (b)., ( ) ( ) ( ) α β a b = d γ δ a = dα, b = dβ, a (d) b (d) (a) + (b) (d)., a, b R, d R (a) + (b) = (d), Bézout. ( ) (2) [4, (3.)] ( ) a, b R, (d) (e) a d, e R b ( ) ( ) a d b e., (a, b) = (d, e) = (d), R Bezout. ( ), R Bezout, m A m n. m =. m >, ( ) a A A. A (m ) (n )., A : c... c 2... A (c i ) (c i+ ). d R (d) = (a, c ), d = ma + nc, a = da and c = dc m, n, a, c R., ( ) ( ) a a ma + nc c c ( d ) a c, A : d... a c... A c ( d a c d c, d.,,. )

54 54 B (3) [2, Theorem 5.2] ( ) R Hermite Bézout. (ii), (4) (a, b, c) = R a, b, c R A = ( a c ) b (7.6.2), P AQ A. P AQ (, ) u. P p, q Q x, y., pax + pby + qcy = u, (pa, pb + qc) = (ii). ( ) ( ),, R. a b 2, (a) + (b) = (d) d R, ap + bq = d, a = sd, b = rd p, q, r, s R. d(ps qr l) =. We dismiss the cased =, and thus have that ps qr is a unit. The observation (6) completes the proof. It was remarked in 2 that diagonal To prove the sufficiency we first observe (Theorem 3.2) that R is an Hermite ring. Given a 2 by 2 matrix, we may thus arrange to get a zero, say in the lower left corner. We thus reach the matrix A of (7.6.2). Write (a, b, c) = d, d = xa + yb + zc, a = axd, b = bxd, c = Cxd. We dismiss the case d = and thus find that xax + ybx + zcx is a unit ; without loss of generality we may change notation and assume (a, b, c) =. We now take the p and q offered us in hypothesis ( ), observe that necessarily (p, q) =, complete the row p, q to a unimodular matrix, and use it to left-multiply A. The result is a matrix with pa, pb + qc for its first row. Right multiplication by a suitable unimodular matrix converts this to,. We sweep out the element in the lower left corner and thus complete the reduction. 7.7 (Abelian sandpile model), Abelian sandpile model (Graph) V ( ) E G = (V, E). (vertex) (edge). V = {, 2, 3, 4}, E = {{, 2}, {, 3}, {2, 3}, {2, 4}, {3, 4}} G, : G = (V, E) G = (V, E). () v V, v deg v = { u {u, v} E } v (degree). (2) (connected). (3) (v, v 2,..., v r ) {v i, v i+ } E (i =, 2,..., r ) (path). (4) (v, v 2,..., v r ) v = v r, (cycle). (5) 2 G = (V, E) G = (V, E ), G G, (i.e., V V E E ) G G (subgraph).

55 *** B ( ) *** () (tree). (2) G = (V, E) G = (V, E ) (spanning tree). (3) (complete graph). n K n (4), (bipertite graph). (5), (complete bipertite graph). m, n K m,n :, K 4,, K 2, ( ) G = (V, E), (chip) σ (configuration)., σ : V N = {,, 2,... },., 7.7. σ() = 2, σ(2) = 4, σ(3) = 3, σ(4) =, G v σ(v) deg(v). v : 7.7. (firing), v,, τ. σ(v) deg(v), if u = v, τ(u) = σ(u) + µ(u, v), if u v.., µ(u, v) u v,. (muliiple edge )., σ 2, τ() = 3, τ(2) =, τ(3) = 4, τ(4) = 2 τ., G w, (sink). w, w

56 56 B : σ 2 τ. (dynamical system) (the abelian sandpile model). v, v deg v. (stable configuration), i.e., σ(v) < deg(v) for v w., w = ,,., w, w. 2,,., τ w = : σ, σ, M. M. σ, σ 2, σ σ 2, σ σ 2,., M ( ). M (ideal) J, J M, σ M σ J J. (sandpile group) (critical group) K(G) M (minimal ideal),,. K(G), w, ( ). [5], 7.7.6, 2,,,, 2 3., σ σ()σ(2)σ(3), M = M M = {,,,, } M = {,,,,, } M = {,,,,, } M = M = M = M = {,,, }

57 *** B ( ) *** w = : G (V, E) τ σ 7.7.7: M σ τ

58 58 B., K(G) = {,,, },, , σ =., K(G) τ σ 7.7.8: K(G) σ τ. [5] K(G) = Z/4Z. G = (V, E) σ σ(v) v V,., G = (V, E), K(G) σ,,.,, : K(G), 2,,. ( [5] )., (sandpile group).

59 *** B ( ) *** ( ). K n K(K n ) = (Z/nZ) n ( ) K m,n K(K m,n ) = (Z/mnZ) (Z/mZ) n 2 (Z/nZ) m G = (V, E). u v µ(u, v) =, µ(u, v) =. deg v v ( v ) G u, v V, L = L(G) = (L uv ) u,v V, G (Laplacian matrix). µ(u, v), u v, L uv = deg(v), u = v., L(G) = deg v L(G), L(G). L = L (G) L (sink). (,, ). (Matrix-Tree Theorem) (e.g., [, Thm ]) det L = κ(g), G (spanning trees). V = n L = L(G) θ,..., θ n. ( θ n = )., (spanning trees) κ(g) = θ θ n /n., det L (G) = det 3 = 8 3., L(G) = 2 2, L (G) = det L (G) = ,,.,., L L Z snf. L (α,..., α n ) L snf (α,..., α n, ).

60 6 B : L (G) e,..., e n, G. K(G) Z/e Z Z/e n Z L (G) = 2 snf 2, K(G) Z/4Z 4

61 8 R- 8. R ( ) R ( ), M R-. M {x λ } λ Λ a i x λi ( ) i M x λ. a i x λi = a i = i {x λ } λ Λ (independent) ( ) R ( ), M R-. K M RK = M, K M (base). M, M R- (free R-module) ,. R,, Zorn R :, M, N : R, R- f : N M, N, M B N = (v,..., v n ), B M = (u,..., u m ), : (i) f(v i ) = e i u i ( i r), f(v i ) = (r < i n), (ii) e i e i+ ( i < r). N, M B N = (v,..., v n), B M = (u,..., u m) A = (a ij ) M m,n (R). (f(v ),..., f(v n)) = (u,..., u m)a P GL n (R), Q GL m (R) e e 2... QAP = e r... = B. e i ( i r) e i e i+ ( i < r). (u,..., u m)q = (u,..., u m ), (v,..., v n)p = (v,..., v n ) (f(v ),..., f(v n )) = (u,..., u m )B.,. 6

62 62 B R, M R m ( ). M R- N,, m.. m. m =. m, m R-. M (x,..., x m ), N M R-. N = {}, N {}. y N y = a x + + a m x m (8..)., f : N R, y a R- f(n) R. R f(n) = (b ) b R., f(y ) = b y N. y = b x + + b m x m. M = Rx Rx m, M m R-,, N = N M, m R-. N (y 2,..., y l ) (l m). (y, y 2,..., y l ) N.... y = a x + + a m x m N, f(y) = a (b ) a = cb c N., y cy = (a 2 cb 2 )x (a m cb m )x m N c 2,..., c l R y cy = c 2 y c l y l. b =, N = N (y 2,..., y l ) N, l m. b., (y, y 2,..., y l )., c y + c 2 y c l y l =. c 2 y c l y l N f(c 2 y c l y l ) =, f c b =. R b c =., c 2 y c l y l =, (y 2,..., y l ) c 2 = = c l =., N, l m R R- M.. M M R R. m R- M R- N r, M B = (x,..., x m ) e,..., e r R,. (i) e i e i+ ( i < r) (ii) (e x,..., e r x r ) N.. N 8..5 R-. N r. f : N M f(x) = x, rank f = dim N = r, 8..4, N (y,..., y r ) M (x,..., x m ) y i = e i x i ( i r), e i e i+ ( i < r).,.

63 *** B ( ) *** Z 3 Z- Zv + Zv 2 + Zv 3. v = 2, v 2 =, v 3 =, Zv + Zv 2 + Zv , ( 2) ( 3) ( ) ( ) ( ) ( 2) 2 2 2, B = = = u = 2, u 2 =, u 3 = 3 2

64 64 B a v + a 2 v 2 + a 3 v 3 = 2 a a 2 = a a 3 a + a 2 + a 3 = 2 a a 3 = (a + a 2 + a 3 )u + (a a 3 )u a a 2 u, u 2 Z-, Z R, M R-, x M A(x) = { a R ax = } R, A(x) x (anihilator). R A(x) = (a) a R. a x (order). a x, R V,. a =, x. R V, V. R- R R, M R-,. () x M R- Rx, R/A(x). (2) R a R/a, R-. (3) R R- N R-.. (), (2). (3) (), (2) ( R- ). R, M R-,. (i) M R- M i. M = M M s (ii) M i R/(a i ) ( i s), a i R a i a i+ ( i < r), (a i ) R. (iii) a i ( i r), R. a j = (r < i s) M M r M, M r+ M s R s r. M (x,..., x m ). m (v,..., v m ) R- V R- f : V M f(a v + + a m v m ) = a x + + a m x m., M V/ Ker f. Ker f R- V R-, 8..7, Ker f µ e,..., e µ R (e v,..., e µ v µ ) Ker f, e i e i+ ( i < µ). Ker f = Re v Re 2 v 2 Re µ v µ

65 *** B ( ) *** 65., λ µ e,..., e λ, e λ+,..., e µ., M V/ Ker f Rv /Re v Rv λ /Re λ v λ Rv λ+ /Re λ+ v λ+ Rv µ /Re µ v µ Rv µ+ Rv m }{{}}{{}}{{} λ t λ m µ. e i, Re i v i = Rv i Rv i /Re i v i = ( i λ)., i > µ e µ+ = = e m = Re i v i = Rv i /Re i v i = Rv i (µ < i m). M V/ Ker f Rv λ+ /Re λ+ v λ+ Rv µ /Re µ v µ Rv µ+ /Re µ+ v µ+ Rv m /Re m v m }{{}}{{} µ λ m µ., r = µ λ, s = m µ (i), (ii). (iii) (i), (ii) (iii) G, x G = y Z 3 x 3 y 2 z = z G Z- M = G. Z- f : Z 3 Z f(x, y, z) = x 3 y 2 z, Ker f Z-. e =, e 2 =, e 3 = f e, e 2, e 3 ( ) ( ) f(e ) f(e 2 ) f(e 3 ) = 3 2 ( ) A = 3 2. A, B =. ( ) A = ( ) v = e, v 2 = 3 e + e 2, v 3 = 2 e + e 3 ( ) ( ) f(v ) f(v 2 ) f(v 3 ) =., Ker f = Zv 2 + Zv 3 Z 2

66 66 B G, G = Z/2Z Z/3Z G Z- M = G. ( ) ( ) + 2Z x =, x 2 = + 3Z. Z- V = Z Z ( ) ( ) e =, e 2 =. Z- f : V M f(e ) = x, f(e 2 ) = x 2, N = Ker f ( ) ( ) 2 y = 2e =, y 2 = 3e 2 = 3 Z R- N R- M R- f : N M, x x N (y, y 2 ) M (x, x 2, x 3 ) ( ) 2 A = 3. A ( ), B = 6 ( ) ( ) 2. = ( ) ( 3) ( ) ( 2) A ( ) ( ) 3 A ( 3 2 ) = ( 2 3 = B ) B

67 *** B ( ) *** 67. ( ) ( ) y 2 = y + y 2 =, y 6 2 = 3y 2y 2 = 3 6 N, M = V/ Ker f Z/Z Z/6Z Z/6Z. ( ) ( ) x 2Z = 2x + 3x 2 = =, x + 2Z 2 = x x 2 = 3Z + 3Z, M x x 4 y 8 z = 8 32x y 2 z = x 2 y 4 z = x 4 y 8 z = 32x y 2 z = 4x 2 y 4 z = A = 32 2, A 2 = 6 = B = 5 7, 2 3 A 2 = 5 7 B., Ker f Z-. Ker f = Z 2, ( 5) 2x = 84., 2 3 x = 7 4 y + 2 z = 2 5

68 68 B. 4 5, x = 7, y =, z =. 2 3 x 7 y = + Z 2 z.

69 [], Galois I,,, 977. [2] I. Kaplansky, Elementary divisors and modules, Trans. Amer. Math. Soc. 66 (949), [3], I,,, 976. [4] M.D. Larsen, W. J. Lewis, and T. S. Shores, Elementary divisor rings and finitely presented modules, Trans. Amer. Math. Soc. 87 (974), [5] L. Levine and J. Propp, WHAT IS a sandpile?, Notices Amer. Math. Soc. 57 (2), [6], Jordan I,,, 977. [7], Jordan II,,, 977. [8] Richard Stanley, Smith Normal Form in Combinatorics arxiv:62.66 [math.co]. [9] Richard Stanley, Enumerative Combinatorics, vol., second edition, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 22. [] Richard Stanley, Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge,