Z.
N.
X
X
b a (a = 0) ,

k b = k a.
a | b
a b,
a b,
b a.
b a, a b.
a, b, c, m " Z, a, m = 0.

(1) a | b a | b c.
(2) a | b b | c, a | c, (b = 0) .

(3) a | b a | c, a | (bx + cy) x, y " Z.
(4) a | b b | a |a| = |b| (b = 0) .

(5) a | b a > 0, b > 0, a d" b.
(6) a | b m a | m b
b a = 0

k r
b = k a + r, 0 d" r < |a| .
a b,
r b a.
a " Z\ {0}
b c a | b a | c.
b c b, c
b c b c
b c (b, c) (b, c) .
 b1, b2, ...bn
(b1, b2, ...bn) .
g = (b, c)
b c x0, y0
g = b x0 + c y0.
b c
b c
(1)
A = {bx + cy : x, y " Z} .
(2) b c
b c
c > 0. b c
b = k1 · c + r1, 0 < r1 < c,
c = k2 · r1 + r2, 0 < r2 < r1,
r1 = k3 · r2 + r3, 0 < r3 < r2,
r2 = k4 · r3 + r4, 0 < r4 < r3,
rj-2 = kj · rj-1 + rj, 0 < rj < rj-1,
rj-1 = kj+1 · rj.
rj b c.
b = 3102 c = 1044.
3102 = 2 · 1044 + 1014,
1044 = 1 · 1014 + 30,
1014 = 33 · 30 + 24,
30 = 1 · 24 + 6,
24 = 4 · 6.
6. (3102, 1044) = 6.
6 = 30 - 1 · 24 = 30 - (1014 - 33 · 30) = 34 · 30 - 1014 =
= 34 · (1044 - 1014) - 1014 = 34 · 1044 - 35 · 1014 =
= 34 · 1044 - 35 · (3102 - 2 · 1044) = (-35) · 3102 + 104 · 1044.
(3102, 1044) = (-35) · 3102 + 104 · 1044.
3102 1044
x0 = -35 y0 = 104.
a1, a2, ..., an
b
a1, a2, ..., an ai | b i " {1, 2, ..., n} .
a1, a2, ..., an
a1, a2, ..., an [a1, a2, ..., an]
(a1, a2, ..., an) .
a1, a2, ..., an
[a1, a2, ..., an] .
(a, b) · [a, b] = a · b, a, b " N.
3102 1044.
(3102, 1044) = 6
3102 · 1044
[3102, 1044] = = 539748.
6
a1, a2, ..., an, b
ai (i " {1, 2, ..., n})
a1x1 + a2x2 + ... + anxn = b
a1, a2, ..., an b.
a, b
(a, b) = 1.
ax + by = c, a, b, c " Z, a2 + b2 > 0,
 (a, b) | c.
" ax + by = 1, a, b " Z, a2 + b2 > 0.
a, b (")
(x0, y0)
ax + by = c, a, b, c " Z, a2 + b2 > 0,
b a
x = x0 + t, y = y0 - t, t " Z.
(a, b) (a, b)
" 435x + 2012y = 6
435 2112 3. (")
3 | 12.
"" 435 · (-335) + 2112 · 69 = (435, 2012) = 3.
("") 2
435 · (-335 · 2) + 2112 · (69 · 2) = 3 · 2 = 6.
435 · (-670) + 2112 · 138 = 6.
(") x0 = -670 y0 = 138.
(")
x = -670 + 704 t, y = 138 + 145 t, t " Z.
n,
n " N\ {1}
1 n.
 a, b, c
(a, b) = 1 a | b · c, a | c.
n
n = p1 · p2 · ... · pk, n = q1 · q2 · ... · ql
n k = l pj qs (j "
{1, 2, ..., k} s " {1, 2, ..., l}),
"
n n.
" n > 1
n
"1 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ....
("1) p1 = 2
2.
"2 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, ....
2 p2 = 3.
3 3.
"3 2, 3, 5, 7, 11, 13, 17, 19, ....
2 3 p3 = 5.
pn.
pn
pn. pn+1.
"" 2, 3, 4, 5..., N,
"
pk d" N.
("") pk
" " " (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ..., 83, 84, 85) .
 p1 = 2.
(2, 3, 5, 7, 9, 11, 13, 15, 17, ..., 83, 85) .
p1 = 2, 2,
3 3 p2 = 3
(2, 3, 5, 7, 11, 13, 17, , ..., 83, 85) .
p2 = 3, 2 3,
5. 5
p3 = 5.
(2, 3, 5, 7, 11, 13, 17, , ..., 83) .
" p4 = 7 7
85 7 7.
(" " ") 2, 3, 5, 7 2, 3, 5, 7
{2, 3, 4, 5, 6, ..., 85}
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83.
Õ : N N Õ (n) , n " N,
n n
Õ
Õ (n) = card {k " N : k d" n '" (k, n) = 1} , n " N,
cardA A A = {k " N :k d" n (k, n) = 1}
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Õ (n) 1 1 2 2 4 2 6 4 6 4 10 4 12 6
 p
Õ (p) = p - 1.
Ä… " N p
Õ (pÄ…) = pÄ…-1 (p - 1)
Õ (pÄ…) = pÄ… - pÄ…-1.
1 2 k
Ä…1, Ä…2, ..., Ä…k " N n = pÄ… pÄ… ... pÄ… p1, p2, ..., pk
1 2 k
1 1 1
Õ (n) = n 1 - 1 - ... 1 - .
p1 p2 pk
n = p1 p2 ... pk p1, p2, ..., pk
Õ (n) = (p1 - 1) (p2 - 1) ... (pk - 1) .
1 2 k
Ä…1, Ä…2, ..., Ä…k " N n = pÄ… pÄ… ... pÄ… p1, p2, ..., pk
1 2 k
1 2 k
Õ (n) = Õ (pÄ… ) Õ (pÄ… ) ... Õ (pÄ… ) .
1 2 k
m, n " N (m, n) = 1,
Õ (m n) = Õ (m) Õ (n) .
n1, n2, ... , nk " N (ni, nj) = 1 i = j (i, j " {1, 2, ...k})

n1, n2, ... , nk
Õ (n1 n2 ... nk) = Õ (n1) Õ (n2) ... Õ (nk) .
a b
m (m " N) , m | (a - b) .
a b m a a" b ( m) .
a a" b ( m) Ð!Ò! " a - b = k m.
k"Z
a"
a, b, c, d m
a a" a ( m) a"
a a" b ( m) b a" a ( m) a"
 a a" b ( m) b a" c ( m) , a a" c ( m) a"
a a" b ( m) (a - b) a" 0 ( m) .
a a" b ( m) c a" d ( m) , a + c a" (b + d) ( m) .
a a" b ( m) c a" d ( m) , a c a" (b d) ( m) .
k k
ai a" bi ( m) ai, bi " Z i " {1, 2, .., k}), ai a" bi ( m) .
i=1 i=1
a a" b ( m) , ak a" bk ( m) , (k " N).
a a" b ( m) d > 0 d | m, a a" b ( d) .
a a" b ( m) c > 0, a c a" b c ( m c) .
c a a" c b ( m) (c, m) = 1 a a" b ( m) .
f
a a" b ( m) , f (a) a" f (b) ( m) .
11 a 11
11.
a a = an (10)n + an-1 (10)n-1 +
... + a110 + a0. 10 a" -1 ( 11) .
f (10) a" f (-1) ( 11) f anxn+an-1xn-1+...+a1x+a0
a = an (10)n+an-1 (10)n-1+...+a110+a0 a" an (-1)n+an-1 (-1)n-1+...+a1 (-1)+a0 ( 11) .
m1, m2, ..., mn (n > 1) ,
(mi, mj) = 1 i = j (i, j "

{1, 2, ..., n}) r1, r2, ..., rn
x a" r1 ( m1) ,
x a" r2 ( m2) ,
"
x a" rn ( mn) .
m = m1 m2 ... mn
x0 (") x
(") x = x0 + k m, m = m1 m2 ... mn
k " Z.
 anxn + an-1xn-1 + ... + a1x + a0 a" 0 ( m)
f (x) = anxn + an-1xn-1 + ... + a1x + a0
m " N. f (c) a" 0 ( m)
f (x) a" 0 ( m) .
c f (x) a" 0 ( m) .
d a" c ( m) d
f (x) a" 0 ( m)
{0, 1, 2, ..., m - 1}
m
f (x) a" 0 ( m)
m
f (x) a" 0 ( m)
m.
x100 - 1 a" 0 ( 5)
1, 2, 3, 4. x = k+5t, k " {1, 2, 3, 4} .
ax a" b ( m)
a, b " Z, m " N, g = (a, m) .
ax a" b ( m)
g | b.
m
g m.
g
ax a" b ( p) p
p a,
" 15x a" 25 ( 35)?
(") g = (15, 35) = 5 5 | 25.
15x - 35y = 25, x, y " Z.
5
3x - 7y = 5.
 x0 = 4, y0 = 1
5 x = 4 + 5s, s " Z.
35
= 7 35
5
7
x = 4 + 35t
x = 11 + 35t
x = 18 + 35t , t " Z.
x = 25 + 35t
x = 32 + 35t
f (x) = anxn+an-1xn-1+...+a1x+a0
p p an,
f (x) a" 0 ( p) n
. p (p - 1)! a" -1 ( p) .
a m " N
aÕ(m) a" 1 ( m) .
a
p
ap-1 a" 1 ( p) .
a
p
ap a" a ( p) .