N = {0, 1, 2, . . . } Z
b
a q
r
a = bq + r
0 d" r < |b|
q a b r
a b a mod b
(q, r)
b
a q r a
0 d" a < b a = 0q + a
b = 0

a = 0 a
a = bq + r
a + 1 a + 1 = bq + (r + 1)
r + 1 < b
r + 1 = b a + 1 = bq + b = b(q + 1) + 0
a
a -a
-a = bq+r
a = b(-q) + (-r)
r = 0
b a = b(-q - 1) + (b - r)
b < 0 -b
a
a = (-b)q + r 0 d" r < -b = |b|
a = b(-q) + r
a b
a = bq + r = bq + r ,
 0 d" r, r < |b|
|b| · |q - q | = |r - r|.
r r -|b| < r - r < |b|
|b|
|b| |b|
|b| |r - r| = 0 |q - q | = 0
b = 0 q = q r = r

b
a
a = a0 + a1b + a2b2 + · · · + asbs, 0 d" ai < b, i = 0, 1, . . . s, as = 0.

a a
b a0 a1 as
a = (asas-1 . . . a1a0)b b
b = 10
1236 = 3 + 2 · 6 + 1 · 62 = 5110 = 51
a a < b s = 0
a0 = a a e" b
a a a
b
a = bq + r, 0 d" r < b.
q
b > 1 q < a
q = a0 + a1b + a 2b2 + · · · + asbs,
s 0 d" ai < b i = 0, 1, . . . , s
as = 0

a = r + bq =
= r + b(a0 + a1b + a 2b2 + · · · + asbs) =
= r + a0b + a1b2 + · · · + asbs+1,
a = b(a1 + a2b + · · · + asbs-1) + a0,
 a0 0 d" a0 < b
B
a
a b
a b
q
a q
a = 2008 b = 8
2008 = 8 · 251 + 0,
251 = 8 · 31 + 3,
31 = 8 · 3 + 7,
3 = 8 · 0 + 3,
 2008 = 37308
2008 0
251 3
31 7
3 3
0
b
2s - 1 s - 1
b2 b3 bs s aibi
a0 + b(a1 + b(a2 + . . . (as-1 + bas) . . . )).
s
b b
B
k b b
B - 1 B
a = a0 + a1B +
a2B2 + · · · + asBs B i
0 d" ai < B B = bk ai
ai = ai,0 + ai,1b + · · · + ai,k-1bk-1
ai,j b k
b b
k
a = a0 + a1B + a2B2 + · · · + asBs =
= a0,0 + a0,1 · b + · · · + a0,k-1 · bk-1 +
+(a1,0 + a1,1 · b + · · · + a1,k-1 · bk-1)bk + · · · +
+(as,0 + as,1 · b + · · · + as,k-1 · bk-1)bks =
= a0,0 + a0,1 · b + · · · + a0,k-1 · bk-1 +
+a1,0bk + a1,1 · bk+1 + · · · + a1,k-1 · b2k-1 + · · · +
+as,0 · bks + as,1 · bks+1 + · · · + as,k-1 · bk(s+1)-1
a b
b
B b
 B k
b
b
k
B
16
A F 16 = 24
0 "! 0000 4 "! 0100 8 "! 1000 C "! 1100
1 "! 0001 5 "! 0101 9 "! 1001 D "! 1101
2 "! 0010 6 "! 0110 A "! 1010 E "! 1110
3 "! 0011 7 "! 0111 B "! 1011 F "! 1111
5A4F16
0101 | 1010 | 0100 | 1111
5A4F16 = 1011010010011112.
a b a | b
c b = ac
a | b Ð!Ò! "c"Zb = ac.
a
a | b
b
0
0 | 0
0
a | b a b
a, b, c " Z
1 | a
a | a
a | b b | c a | c
a | b b | a |a| = |b|
 a | b (-a) | b a | (-b)
a = 0 a | b b mod a = 0

a | b a | c a | b Ä… c
a | b a | bc
a, b " Z
d
d > 0
d | a d | b
´ ´ | a ´ | b ´ | d
a b
d"
a = b = 0
(a, b)
(0, 0)
(a, b)
(a, b) d d
d ´
a b d d d
a b d | d d | d
|d| = |d |
d d d = d
a b
NWD(a, b)
a, b " Z
NWD(a, b) = NWD(b, a)
NWD(a, b) = NWD(|a|, |b|)
 NWD(a, b) = NWD(a Ä… b, b)
b = 0 NWD(a, b) = NWD(a mod b, b)

a b
d = NWD(a, b)
d NWD a
a Ä… b d > 0 d
a b d a b
aÄ…b
´ a Ä… b b a = (a Ä… b) " b
´ a
b d = NWD(a, b) ´ d
a mod b = a - qb
q
a = 0 NWD(a, 0) = |a|

NWD(a, b)
a b
NWD(a1, a2) a1 e" a2 e" 0
a1 = max(|a|, |b|) a2 = min(|a|, |b|) a2 = 0
a1 = 0 a1
a2 = 0 a1

a2
a1 = q1a2 + a3, 0 d" a3 < a2.
NWD(a1, a2) = NWD(a2, a3)
a3 = 0 NWD(a2, a3) = a2
NWD(a1, a2)
a2 a3
a2 = q2a3 + a4 0 d" a4 < a3.
NWD(a1, a2) = NWD(a2, a3) = NWD(a3, a4) = . . . ,
 ai+1 ai-1
ai
NWD(ai, ai+1) ai
(a, b) (0.0)
(a, b) = (0, 0)

NWD(a, b)
(a, b) = (0, 0) a1, a2, a3, . . .

a1 e" a2 > a3 > a4 > . . . .
NWD
a1, a2, a3, . . .
a b
NWD(a, b)
a := |a| b := |b|;
a < b a b
a = 0
b = 0

c := a mod b
a := b b := c
a
 a e" b > 0
a b
a b s
a b
s a > b e" 0
a1 = a a2 = b
a1 = q1a2 + a3, 0 < a3 < a2,
a2 = q2a3 + a4, 0 < a4 < a3,
as-1 = qs-1as + as+1, 0 < as+1 < as,
as = qsas+1 + 0.
as+1 a1 a2 as as+1
a i = ai/as+1
(a/as+1, b/as+1) a b
ai qi
a1 a2
q1 = q2 = · · · = qs = 1.
as = as+1 = 1 ak-1 = ak + ak+1 k = 2, 3, . . . , s
bi = as+2-i i = 1, 2, . . . , s + 1
ai b1, b2, . . . , bs+1
b1 = b2 = 1,
bi+2 = bi+1 + bi i = 1, 2, . . . , s - 1.
" i
1 1 + 5
bi H" " ,
2
5
bs = a2 = b
1/2 log 5 + log b
s H" ,
log Å‚
"
1+ 5
Å‚ =
2
log2 b b
 b
C a >
b > 0 C log2 b
NWD
a b
log2 a log2 b
(a, b) = (0, 0)

Ä… ² NWD(a, b) = Ä…a + ²b
a e" b e" 0
NWD(a, b) a1 = a a2 = b
a1 = q1a2 + a3, (R1)
a2 = q2a3 + a4, (R2)
. . .
ai = qiai+1 + ai+2, (Ri)
. . .
as-2 = qs-2as-1 + as, (Rs-2)
as-1 = qs-1as + as+1, (Rs-1)
as = qsas+1 + 0. (Rs)
NWD(a, b) = as+1
as-1 as (Rs)
NWD(a, b) = 1 · as-1 + (-qs-1) · as.
as-1 as
NWD(a, b) = Ä…s-1 · as-1 + ²s-1 · as.
 (Rs-2)
as = 1 · as-2 + +(-qs-2) · as-1.
as NWD(a, b)
NWD(a, b)
as-2 as-1
NWD(a, b) = Ä…s-2 · as-2 + ²s-2 · as-1.
NWD(a, b)
Ä… ²
NWD(49, 18)
49 = 2·18 + 13
18 = 1·13 + 5
13 = 2· 5 + 3
5 = 1· 3 + 2
3 = 1· 2 + 1
2 = 2· 1 + 0
Ä… · 49 + ² · 18
13 = 1·49 + (-2)·18
5 = 1·18 + (-1)·13
3 = 1·13 + (-2)· 5
2 = 1· 5 + (-1)· 3
1 = 1· 3 + (-1)· 2
1 = 1 · 3 + (-1) · 2 =
= 1 · 3 + (-1) · [1 · 5 + (-1) · 3] =
= (-1) · 5 + 2 · 3 =
= (-1) · 5 + 2 · [1 · 13 + (-2) · 5] =
= 2 · 13 + (-5) · 5 =
= 2 · 13 + (-5) · [1 · 18 + (-1) · 13] =
= (-5) · 18 + 7 · 13 =
= (-5) · 18 + 7 · [1 · 49 + (-2) · 18] =
= 7 · 49 + (-19) · 18.
k (Ä… - kb)a + (² + ka)b = Ä…a + ²b
Ä… ²
b = 0 Ä…

b a = 0 ²

a
NWD(a, b)
a b Ä…
²
a e" b > 0 a1 = a a2 = b
NWD(a, b)
a b
a b
a1 = 1 · a + 0 · b
a2 = 0 · a + 1 · b.
a3 = a1 - q1a2 q1
a1 a2
a3 a b
q1
ai-1 = Ä…i-1 · a + ²i-1 · b
ai = Ä…i · a + ²i · b,
 ai+1
qi-1 ai-1 ai
ai Ä…i ²i
(i + 1)
i - 1 i
NWD(206, 174)
a Ä… ²
206 1 0
174 0 1
a Ä… ² q
206 1 0 -
174 0 1 1
32 1 -1 5
14 -5 6 2
4 11 -13 3
2 -38 45 2
0 - - -
NWD(206, 174) = 2 = (-38) · 206 + 45 · 174.
a b
NWD(a, b) = 1
a b
Ä… ² Ä…a + ²b = 1
NWD(a, b) = 1 Ä… ²
Ä…a + ²b = 1 d = NWD(a, b)
d | a d | b d | Ä…a + ²b = 1
d = 1 a b
c | ab NWD(a, c) = 1 c | b
 a c
Ä… ²
Ä… · a + ² · c = 1.
b
Ä… · (ab) + (²b)c = b.
c
c c | b
n > 1
n n = 2
n = 2 n0
n 1 < n < n0 n0
n0
n0 d n0
1 < d < n0 p
d p n0
n
n e" 2
p d" n
 n
p
p
p p
p
p
n - 1 n - 1
p1, p2, . . . , ps N = p1p2·
· · · · ps + 1
i 1 d" i d" s pi | N pi
p1p2 · · · · · ps pi N - p1p2 · · · · · ps = 1
z = 0

z = µ · p1p2 · · · · · ps,
µ = Ä…1 s p1 p2 ps
 z z
z = 1
s = 0 z > 1 n 1 < n < z
z
p z = p
s = 1 z/p
1 < z/p < z
z/p = p1p2 . . . ps z = p1p2 . . . ps · ps+1
ps+1 = p
p
q1 q2 qt p = qi i = 1, 2, . . . , t
t t = 1
p q1 p = q1
t p
q1 q2 qt+1 p = qt+1
p qt+1 NWD(p, qt+1) = 1
p | q1q2 · · · · · qt
µ
p1p2 · · · · · ps = q1q2 · · · · · qt
s t p1, p2, . . . , ps, q1, q2, . . . , qt
s = t p1, p2, . . . , ps
q1, q2, . . . , qs s s = 0
t > 0
s = t = 0
s
t p1 ps q1 qt p1p2 ·
· · · · ps = q1q2 · · · · · qt s = t p1 ps
q1 qt p1p2 · · · · · psps+1 = q1q2 · · · · · qt ps+1
ps+1 = qi i
a b
a = p1p2 · · · · · ps b = q1q2 · · · · · qt
NWD(a, b)
 NWD
a = 3127 b = 2491 NWD(a, b)
NWD(a, b) = 53
p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, p6 = 13, p7 = 17, . . . .
p1 = 2, p2 = 3
n e" 1
(n + 1)! + 2, (n + 1)! + 3, (n + 1)! + 4, . . . , (n + 1)! + (n + 1)
n
x
Ä„(x) p x
Ä„(x)
lim = 1.
x"
x/ ln(x)
x
x Ä„(x)
ln(x)
x
x Ä„(x)
ln(x)
m
a b m
m | (a - b)
a a" b (mod m).
m m
a mod m
a a" b (mod m)
m n a b c d
a a" a (mod m)
a a" b (mod m) b a" a (mod m)
a a" b (mod m) b a" c (mod m) a a" c (mod m)
a a" b (mod m) a + c a" b + c (mod m) ac a" bc (mod m)
a a" b (mod m) c a" d (mod m) a + c a" b + d (mod m)
ac a" bd (mod m)
a a" b (mod m) an a" bn (mod mn)
a a" b (mod m) a mod m = b mod m
 ad a" bd (mod md) d > 0 a a" b (mod m)
ad a" bd (mod m) NWD(m, d) = 1 a a" b (mod m)
m
m
s
ai · 10i a" a0 (mod 2),
i=0
10 a" 0 (mod 2)
10i a" 0 (mod 2) i e" 1
i ai
s
ai · 10i a" 0 (mod 2) a0
i=1
m = 3 m = 9
s s
ai · 10i a" ai (mod m).
i=0 i=0
m = 3 10 a" 1 (mod m)
10i a" 1 (mod m) i e" 1
i = 0 i
ai
s s
ai · 10i a" (-1)iai (mod 11).
i=0 i=0
10 a" -1 (mod 11)
(. . . a5, a4, a3, a2, a1, a0)10 a"
a" (a2, a1, a0)10 - (a5, a4, a3)10 + (a8, a7, a6)10 - . . . (mod 7).
 1000 a" -1 (mod 7)
(a1, a2, . . . , a13)
1 · a1 + 3 · a2 + 1 · a3 + 3 · a4 + · · · + 3 · a12 + 1 · a13 a" 0 (mod 10).
(a1, a2, . . . , ai, . . . , a13)
(a1, a2, . . . , a i, . . . , a13)
a1 + 3a2 + . . . +wiai+· · · + a13 a" 0 (mod 10)
a1 + 3a2 + . . . +wia i+· · · + a13 a" 0 (mod 10),
w1 i
wi(ai - a i) a" 0 (mod 10).
wi 10
wi
ai - a i a" 0 (mod 10).
ai a i -9 9
10 ai = a i
 10
9
b10 X
10
b1 + 2b2 + 3b3 + · · · + 9b9 + 10b10 a" 0 (mod 11).
. . . 27 . . . . . . 72 . . .
m C C = 0
m
w1, w2, . . . (a1, a2, . . . , an)
w1a1 + w2a2 + · · · + wnan a" C (mod m).
i wi m
i wi+1 - wi m
26
35 1010 1010 0070 5422 2100 0000
k1k2 b1b2b3b4 b5b6b7b8 n1n2n3n4 n5n6n7n8 n9n10n11n12 n13n14n15n16,
k1k2 b1 b8
n1 n16
PL k1k2 b1b2b3b4 b5b6b7b8 n1n2n3n4 n5n6n7n8 n9n10n11n12 n13n14n15n16.
PL k1k2
1010 1010 0070 5422 2100 0000 PL 35;
A Z 10 35
PL
2521
30
101 010 100 070 542 221 000 000 252 135;
97
x
x a" b (mod m).
x x
b m
{b + km|k " Z}.
m
x0 = b mod m.
ax a" b (mod m).
NWD(a, m) | b.
a x a" b (mod m ),
a = a/d b = b/d m = m/d d = NWD(a, m)
NWD(a , m ) = 1
a m
Ä… µ
Ä…a + µm = 1.
a m Ä…a a" 1 (mod m)
Ä…
x a" bÄ… (mod m),
a
x a" a1 (mod m1),
x a" a2 (mod m2).
m1 m2
a1 a2 x0
m1m2
x0 m1m2
m1 m2
µ1 µ2
µ1m1 + µ2m2 = 1.
a1 a2
a1µ1m1 + a1µ2m2 = a1,
a2µ1m1 + a2µ2m2 = a2.
 a1µ2m2 a1
m1
m1
a2µ1m1
m2
a2µ1m1 + a1µ2m2
x0 = a2µ1m1 + a1µ2m2 mod m1m2
x x
m1m2
x a" a1 (mod m1) x a" a1 (mod m1)
x - x a" 0 (mod m1) x - x = km1 k " Z
x - x a" 0 (mod m2)
m2 | x - x = km1 m1 m2 m2
k k = k m2 k " Z x - x = k m1m2
(m1, m2)
m1m2
m2
m1
(m2 - m1)x a" a1m2 - a2m1 (mod m1m2).
m1 m2 NWD(m2 -
m1, m1m2) = 1
m1, m2, . . . , ms
a1, a2, . . . , as
Å„Å‚
x a" a1 (mod m1),
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
x a" a2 (mod m2),
òÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ół
x a" as (mod ms).
x0
m1m2 . . . ms x0
m1m2 . . . ms
 s
p a p
ap-1 a" 1 (mod p).
Z" p
p
fa : Z" Z" fa(x) = ax mod (p)
p p
fa fa(x ) =
fa(x )
ax a" ax (mod p).
p p a a p
a
x a" x (mod p),
x x p
fa
(fa(1), fa(2), . . . , fa(p - 1))
(1, 2, . . . , p - 1)
fa(1) · fa(2) · · · · · fa(p - 1) = 1 · 2 · · · · · (p - 1).
fa(1) · fa(2) · · · · · fa(p - 1) a" (1a) · (2a) · · · · · (a(p - 1)) = ap-1 · 1 · 2 · · · · · (p - 1),
a" p
ap-1 · 1 · 2 · · · · · (p - 1) a" 1 · 2 · · · · · (p - 1) (mod p).
p-1 p
p q
n = pq e
(p - 1)(q - 1) (n, e)
n
 a (n, e)
s = ae mod n.
NWD(e, (p - 1)(q - 1)) = 1 d
k
ed - k(p - 1)(q - 1) = 1.
(n, d)
sd mod n.
a
sd a" (ae)d = aed = a1+k(p-1)(q-1),
a" n
p q n = pq
a " Z k " N
a1+k(p-1)(q-1) a" a (mod n).
a p
ap-1 equiv1 (mod p).
k(q - 1)
a
a1+k(p-1)(q-1) a" a (mod p).
a p
p
a
q p q
p q n = pq
a
a
n