Джумадильдаев А.С. Элементы дискретной математики (часть 1)
Подождите немного. Документ загружается.
1
(1 − x)
3
=(
i≥0
i +2
2
x
i
.
k =3
(1 + x + x
2
+ ···+ x
30
)(1 + x + x
2
+ ···+ x
40
)(1 + x + x
2
+ ···+ x
50
)
=(
i≥0
i +2
2
x
i
)(1 − x
31
− x
41
− x
51
+ O(x
70
)).
x
70
70 + 2
2
−
70 + 2 − 31
2
−
70 + 2 − 41
2
−
70 + 2 − 51
2
= 1061.
x
1
+···+x
k
= n
x
i
∈ N,i=1,...,k, x
1
+ ···+ x
k
= n,
y
i
= x
i
−1 ∈ Z
+
,i=1,...,k, y
1
+ ···+ y
k
= n −k.
y
1
+ ···+ y
k
= n − k
x
1
+ ···+ x
k
= n
x
i
= y
i
+1,i =1,...,k. y
1
+ ···+ y
k
= m
m+k− 1
k−1
x
1
+ ···+ x
k
= n
n−k+k−1
k−1
n−1
k−1
.
(x+1)
n
n
0
,
n
1
,
n
2
,...,
n
n
, 0, 0,....
n ∈ Z
+
(x+1)
−n
−n
0
,
−n
1
,
−n
2
,....
0, 1, 4, 9, 16,....
x+1
(1−x)
3
.
x
5
(1 − 2x)
−7
.
x
8
1
(x−3)(x−2)
2
.
x
15
(x
2
+ x
3
+ x
4
+ ···)
4
.
n, m, k ∈ Z
+
n+m
k
=
k
i=0
n
i
m
k−i
.
(x +1)
m+n
=(x +1)
m
(x +1)
n
.
n k
x
α
1
1
···x
α
k
k
, α
1
+ ...+ α
k
= n, α
1
,...,α
k
∈ Z
+
n+k−1
k
p
0
(n) n
p
0
(3) = 4, 3=1+1+1, 3=1+2, 3=2+1, 3=3. p
0
(n).
p
0
(n)=2
n−1
.
p
n
n
p
1
=1: 1=1;
p
2
=2: 2=2, 2=1+1;
p
3
=3: 3=3, 3=2+1, 3=1+1+1;
p
4
=5: 4=4, 4=3+1, 4=2+2, 4=2+1+1, 4=1+1+1+1;
p
5
=7: 5=5, 5=4+1, 5=3+2, 5=3+1+1, 5=2+2+1,
5=2+1+1+1, 5=1+1+1+1+1.
G(p)=
i≥1
(1 − x
i
)
−1
.
a, b, c, q, r ∈ Z.
d|a d a, a = dq,
q ∈ Z.
a b b|a.
a
b b|a.
a, b (a, b)
d
1
|a, d
1
|b ⇒ d
1
| (a, b)
(18, 30) = 6.
(a, b)
a|c, b|c ⇒ (a, b)|c
(18, 30) = 90.
• N {1, 2, 3,...}
• Z
{...,−3, −2, −1, 0, 1, 2, 3,...}
• Z
+
{0, 1, 2,...}
• Q
{p/q : p, q ∈ Z,q =0}
• R
• C
•α α ∈ R n ∈ Z n ≤ α<n+1.
•α
α ∈ R n ∈ Z n − 1 <α≤ n.
n ∈ N n
n = p
α
1
1
···p
α
k
k
,p
1
<p
2
< ···<p
k
.
a, b ∈ Z,b =0.
a = bq
0
+ r
1
, 0 <r
1
<b,
b = r
1
q
1
+ r
2
, 0 <r
2
<r
1
,
r
1
= r
2
q
2
+ r
3
, 0 <r
3
<r
2
,
r
k−1
= r
k
q
k
k.
(a, b)=r
k
.
a = 7228,b= 378.
7228 = 378 × 19 + 46,
378 = 46 × 8+10,
46 = 10 × 4+6,
10 = 6 × 1+4,
6=4× 1+2,
4=2× 2+0.
7228 |378
−7182 19
378 |46
−368 8
46 |10
−40 4
10 |6
−6 1
6 |4
−4 1
4 |2
−4 2
0
(7228, 378) = 2.
n>1
n
7
6
p
1
<...<p
n
p
1
···p
n
+1. >p
n
.
n ∈ N n =
p
α
1
1
···p
α
k
k
p
1
< ···<p
k
α
1
,...,α
k
∈ N.
n = q
β
1
1
···q
β
r
r
, q
1
< ···<q
r
β
1
,...,β
r
∈ N,
k = r α
1
= β
1
,...,α
k
= β
k
.
n = p
α
1
1
···p
α
k
k
p
1
< ···<p
k
α
1
,...,α
k
∈ N,
5040 = 2
4
× 3
2
× 5
1
× 7
1
5040.
6, 28 12 = 1+2+3+6 56 =
1+2+4+7+14+28.
r
1
,...,r
n
b|a
1
,...,b|a
n
⇒ b|r
1
a
1
+ ···r
n
a
n
.
n n
5
−n
H
n
=1+
1
2
+ ···+
1
n
k 2
k
≤ n P
n. 2
k−1
PH
n
2
k−1
P
1
2
k
1
3
+
1
5
+ ···+
1
2n+1
, n>0
S
n
=
1
3
+
1
5
+ ···+
1
2n+1
. k
3
k
≤ 2n +1 P
2n+1. 3
k−1
PS
n
3
k−1
P
1
3
k
n ∈ N
(a + b)
n
n 2
k
− 1.
p
p n!
k>0
n
p
k
100!
100! s 100!
10
s
, s 100! = 2
α
1
3
α
2
5
α
3
···
α
3
=
i≥1
100/5
i
=20+4=24,
α
1
=
i≥1
100/2
i
=50+25+12+6+3+1> 24 = α
3
,
10
s
=2
s
5
s
, s =24.
100! 24
100!
100! log
10
100! = 158
20!
20! 2, 3, 5, 7, 11, 13, 17, 19
20!
20 = 2
α
1
3
α
2
5
α
3
7
α
4
11
α
5
13
α
6
17
α
7
19
α
8
.
α
1
= 20/2 + 20/4 + 20/8 + 20/16 =10+5+2+1=18,
α
2
= 20/3 + 20/9 =6+2=8,
α
3
= 20/5 =4,
α
4
= 20/7 =2,
α
5
= 20/11 =1,
α
6
= 20/13 =1,
α
7
= 20/17 =1,
α
8
= 20/19 =1.
20! = 2
18
· 3
8
· 5
4
·7
2
· 11 · 13 · 17 · 18.
65
520 1139 1288 162 56 543 831.
n a
n
+ b
n
a + b
a
n
+ b
n
=(a + b)
n−1
i=0
a
i
b
n−i−1
.
n ∈ N. a
n
− b
n
a − b.
a
n
− b
n
=(a − b)
n−1
i=0
a
i
b
n−i
.
2
n
−1 n
n n = ab, a > 1,b>1. 2
n
−1=
2
ab
− 1=(2
a
)
b
− 1 2
a
− 1. 2
n
− 1 > 2
a
− 1 > 1,
2
n
− 1 n
2
n
− 1
2
n
+1 n
n n
n =2
s
a, a a>1. 2
n
+1 = 2
ab
+1 =
(2
a
)
b
+1 2
a
+1. 2
n
+1> 2
a
+1> 1, 2
n
+1
2
k+1
−1 2
k
(2
k+1
−1)
2
k+1
− 1 N =2
k
(2
k+1
− 1)
D(N)={2
i
, 2
i
(2
k+1
− 1) | 0 ≤ i ≤ k}.
d|N
=
k
i=0
2
i
+
i≥0
2
i
(2
k+1
− 1) = (
k
i=0
2
i
)(2
k+1
−1+1)=(2
k+1
− 1)2
k+1
=2N.
N
2
k
(2
k+1
−1) 2
k+1
−1
a, b ∈ Z. a ≡ b(mod m) a − b
m. a b m.
63 ≡ 18(mod15).
a ≡ b(mod m)
m m.
m =5
¯
0={0, ±5, ±10 ± 15, ···},
¯
1={1, 6, 11, ···, −4, −9, ···},
¯
2={2, 7, 17, ···, −3, −8, ···},
¯
3={3, 8, 13, ···, −2, −7, ···},
¯
4={4, 9, 14, ···, −1, −6, −11, ···}.
ax ≡ b(mod m)
m
d = (a, m). ax ≡ b(mod m)
d|b. d
ax ≡ b(mod m) ax+my = b
m
a
1
x ≡ b
1
(mod m
1
),
a
2
x ≡ b
2
(mod m
2
),
a
n
x ≡ b
n
(mod m
n
)
x ≡ b
1
(mod m
1
),
x ≡ b
2
(mod m
2
),
x ≡ b
n
(mod m
n
).
x ≡ b
1
(mod m
1
),
x ≡ b
2
(mod m
2
).
x = b
1
+m
1
t.
m
1
t = b
2
− b
1
(mod m
2
).
(m
1
,m
2
)|b
2
− b
1
.
m
2
/ (m
1
,m
2
):
t ≡ t
0
(mod
m
2
(m
1
,m
2
)
).
x = b
1
+ m
1
(t
0
+
m
2
(m
1
,m
2
)
t)=b
0
+
m
1
m
2
(m
1
,m
2
)
t = b
0
+ (m
1
,m
2
)t
(m
1
,m
2
).
(m
1
,...,m
n
).
m
1
,m
2
,...,m
n
x
i
m
1
···m
i−1
x
i
m
i+1
···m
n
≡ 1(mod m
i
),
i =1, 2,...,n.
x = m
2
m
3
···m
n
x
1
b
1
+ m
1
m
3
···m
n
x
2
b
2
+ ···+ m
1
m
2
···m
n−1
x
n
b
n
x ≡ b
1
(mod m
1
),
x ≡ b
2
(mod m
2
),
x ≡ b
n
(mod m
n
)
m
1
m
2
···m
n
.
x ≡ 2(mod 5)
x ≡ 3(mod 6)
x ≡ 4(mod 7)
m
1
=5,m
2
=6,m
3
=7.
x
1
×6 × 7 ≡ 1(mod 5) ⇒ x
1
≡ 3(mod 5),
x
2
×5 × 7 ≡ 1(mod 6) ⇒ x
2
≡−1(mod 6),
x
3
×5 × 6 ≡ 1(mod 7) ⇒ x
3
≡ 4(mod 7).
x =6×7 × 3 × 2+5× 7 × (−1) × 3+5× 6 × 4 × 4 = 627
a, b ∈ Z,b > 0.
a = bq
0
+ r
1
, 0 <r
1
<b,
b = r
1
q
1
+ r
2
, 0 <r
2
<r
1
,
r
1
= r
2
q
2
+ r
3
, 0 <r
3
<r
2
,
r
k−1
= r
k
q
k
k.
a
b
q
0
+
1
q
1
+
1
q
2
+ ···
1
q
k−1
+
1
q
k
a/b =[q
0
,q
1
,...,q
k
].
a = 3614/189.
3614 = 189 × 19 + 23,
189 = 23 × 8+5,
23 = 5 × 4+3,
5=3× 1+2,
3=2× 1+1,
2=1× 2+0.
3614
189
=19+
1
8+
1
4+
1
1+
1
1+
1
2
3614/189 = [19, 8, 4, 1, 1, 2].
a/b =[q
0
,q
1
,...,q
k
]
δ
0
=
q
0
1
,
δ
1
= q
0
+
1
q
1
,
δ
k
= q
0
+
1
q
1
+
1
q
2
+ ···
1
q
k−1
+
1
q
k
.
δ
0
=
P
0
Q
0
,δ
1
=
P
1
Q
1
, ···δ
s
=
P
s
Q
s
, ···,δ
k
=
P
k
Q
k
.
P
s
,Q
s
P
0
= q
0
,Q
0
=1,
P
s
= P
s−1
q
s
+ P
s−2
,Q
s
= Q
s−1
q
s
+ Q
s−2
,s=1, 2,...,k.
s =0, 1
s.
[q
0
,q
1
,...,q
s+1
]=[q
0
,q
1
,...,q
s−1
,q
s
+
1
q
s+1
],
q
s
= q
s
+ q
−1
s+1
,
(s +1)
δ
s+1
s
δ
s+1
=[q
0
,q
1
,...,q
s−1
,q
s
].
q
s
q
s
. δ
s+1
= P
s+1
/Q
s+1
s
P
s+1
= P
s−1
q
s
+ P
s−2
= P
s−1
(q
s
+ q
−1
s+1
)+P
s−2
,
Q
s+1
= Q
s−1
q
s
+ Q
s−2
= Q
s−1
(q
s
+ q
−1
s+1
)+Q
s−2
.
P
s+1
Q
s+1
=
P
s−1
(q
s
+ q
−1
s+1
)+P
s−2
Q
s−1
(q
s
+ q
−1
s+1
)+Q
s−2
=
P
s−1
q
s
+ P
s−2
+ P
s−1
q
−1
s+1
Q
s−1
q
s
+ Q
s−2
++q
−1
s+1
Q
s−1
=
P
s
+ P
s−1
q
−1
s+1
Q
s
+ Q
s−1
q
−1
s+1
=
P
s
q
s+1
+ P
s−1
Q
s
q
s+1
+ Q
s−1
.
P
s
Q
s
s 0 1 2 ··· s ··· k
q
s
q
0
q
1
q
2
··· q
s
··· q
k
P
s
1 P
0
= q
0
P
1
= P
0
q
1
+1 P
2
= P
1
q
2
+ P
0
··· P
s
= P
s−1
q
s
+ P
s−2
··· P
k
Q
s
0 Q
0
=1 Q
1
= q
1
Q
2
= Q
1
q
2
+ Q
0
··· Q
s
= Q
s−1
q
s
+ Q
s−2
··· Q
k
3614/189
3614/189 = [19, 8, 4, 1, 1, 2].