|
Notation
Z
the set of integers
Z
n
the set of integers modulo
n
N
the set of positive integers
N
0
the set of nonnegative integers
Q
the set of rational numbers
Q
+
the set of positive rational numbers
Q
≥
the set of nonnegative rational numbers
Q
n
the set of
n
-tuples of rational numbers
R
the set of real numbers
R
+
the set of positive real numbers
R
≥
the set of nonnegative real numbers
R
n
the set of
n
-tuples of real numbers
C
the set of complex numbers
|
A
|
the number of elements in the set
A
A
⊂
B
A
is a proper subset of
B
A
⊆
B
A
is a subset of
B
A
\
B
A
without
B
(set difference)
A
∩
B
the intersection of sets
A
and
B
A
∪
B
the union of sets
A
and
B
a
∈
A
the element
a
belongs to the set
A
n
|
m
n
divides
m
gcd
(
m
,
n
)
the greatest common divisor of
m
,
n
lcm
(
m
,
n
)
the least common multiple of
m
,
n
π(
n
)
the number of primes
≤
n
τ(
n
)
number of divisors of
n
σ(
n
)
sum of all positive divisors of
n
a
≡
b
(
mod
m
)
a
and
b
are congruent modulo
m
ϕ
Euler’s totient function
ord
m
(
a
)
order of
a
modulo
m
μ
M¨obius function
xviii
Notation
a
k
a
k
−
1
· · ·
a
0
(
b
)
base-
b
representation
S
(
n
)
the sum of the digits of
n
(
f
1
,
f
2
, . . . ,
f
m
)
factorial base expansion
x
floor of
x
x
ceiling of
x
{
x
}
fractional part of
x
e
p
Legendre function
p
k
n
p
k
fully divides
n
f
n
Fermat number
M
n
Mersenne number
a
p
Legendre symbol
F
n
Fibonacci number
L
n
Lucas number
P
n
Pell number
n
k
binomial coefficient
I
Fundamentals
1
Divisibility
1.1
Divisibility
For integers
a
and
b
,
a
=
0, we say that
a divides
b if
b
=
ac
for some integer
c
.
We denote this by
a
|
b
. We also say that
b
is divisible by
a
or that
b
is a multiple
of
a
.
Because 0
=
a
·
0, it follows that
a
|
0 for all integers
a
. We have 0
|
0, since
0
=
0
·
0.
Straight from the definition we can derive the following properties:
1. If
a
|
b
,
b
=
0, then
|
a
| ≤ |
b
|
;
2. If
a
|
b
and
a
|
c
, then
a
|
α
b
+
β
c
for any integers
α
and
β
;
3. If
a
|
b
and
a
|
b
±
c
, then
a
|
c
;
4.
a
|
a
(reflexivity);
5. If
a
|
b
and
b
|
c
, then
a
|
c
(transitivity);
6. If
a
|
b
and
b
|
a
, then
|
a
| = |
b
|
.
The following result is called the
division algorithm
, and it plays an important
role:
Theorem.
For any positive integers a and b there exists a unique pair
(
q
,
r
)
of
nonnegative integers such that
b
=
aq
+
r
,
r
<
a
.
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_1,
3
4
I Fundamentals, 1. Divisibility
Proof.
Since
a
≥
1, there exist positive integers
n
such that
na
>
b
(for example,
n
=
b
is one such). Let
q
be the least positive integer for which
(
q
+
1
)
a
>
b
.
Then
qa
≤
b
. Let
r
=
b
−
aq
. It follows that
b
=
aq
+
r
and 0
≤
r
<
a
.
For the uniqueness, assume that
b
=
aq
+
r
, where
q
and
r
are also non-
negative integers satisfying 0
≤
r
<
a
. Then
aq
+
r
=
aq
+
r
, implying
a
(
q
−
q
)
=
r
−
r
, and so
a
|
r
−
r
. Hence
|
r
−
r
| ≥
a
or
|
r
−
r
| =
0. Because
0
≤
r
,
r
<
a
yields
|
r
−
r
|
<
a
, we are left with
|
r
−
r
| =
0, implying
r
=
r
and, consequently,
q
=
q
.
In the theorem above, when
b
is divided by
a
,
q
is called the
quotient
and
r
the
remainder
.
Remark.
The division algorithm can be extended for integers as follows: For any
integers
a
and
b
,
a
=
0, there exists a unique pair
(
q
,
r
)
of integers such that
b
=
aq
+
r
,
0
≤
r
<
|
a
|
.
Example.
Prove that for all positive integers
n
, the fraction
21
n
+
4
14
n
+
3
is irreducible.
(1st International Mathematical Olympiad)
Indeed, from the equality
2
(
21
n
+
4
)
−
3
(
14
n
+
3
)
= −
1
it follows that 21
n
+
4 and 14
n
+
3 have no common divisor except for 1; hence
the conclusion.
Problem 1.1.1.
Prove that for all integers n:
(a) n
5
−
5
n
3
+
4
n is divisible by
120
;
(b) n
2
+
3
n
+
5
is not divisible by
121
.
Solution.
(a)
n
5
−
5
n
3
+
4
n
=
n
(
n
2
−
1
)(
n
2
−
4
)
=
n
(
n
−
1
)(
n
+
1
)(
n
−
2
)(
n
+
2
),
the product of five consecutive integers:
n
−
2,
n
−
1,
n
,
n
+
1,
n
+
2.
If
n
∈ {−
2
,
−
1
,
0
,
1
,
2
}
we get
n
5
−
5
n
3
+
4
n
=
0 and the property holds.
If
n
≥
3 we can write
n
5
−
5
n
3
+
4
n
=
5
!
n
+
2
5
=
120
n
+
2
5
,
and the conclusion follows.
1.1. Divisibility
5
If
n
≤ −
3, write
n
= −
m
, where
m
≥
3, and obtain
n
5
−
5
n
3
+
4
n
= −
120
m
+
2
5
,
and we are done.
(b) Observe that
n
2
+
3
n
+
5
=
(
n
+
7
)(
n
−
4
)
+
33
,
so that 11
|
n
2
+
3
n
+
5 if and only if 11
|
(
n
+
7
)(
n
−
4
)
. Thus, if 11
(
n
+
7
)(
n
−
4
)
then 11 (and hence 121) does not divide
n
2
+
3
n
+
5. So, assume 11 divides
(
n
+
7
)(
n
−
4
)
. Then 11
|
n
+
7 or 11
|
n
−
4; but then 11 must divide both of
n
+
7 and
n
−
4, since
(
n
+
7
)
−
(
n
−
4
)
=
11. Thus, 121
|
(
n
+
7
)(
n
−
4
)
.
However, 121
33. So 121
n
2
+
3
n
+
5
=
(
n
+
7
)(
n
−
4
)
+
33. Hence, in all
cases, 121
n
2
+
3
n
+
5.
Problem 1.1.2.
Let a
>
2
be an odd number and let n be a positive integer. Prove
that a divides
1
a
n
+
2
a
n
+ · · · +
(
a
−
1
)
a
n
.
Solution.
Define
k
=
a
n
and note that
k
is odd. Then
d
k
+
(
a
−
d
)
k
=
a
[
d
k
−
1
−
d
k
−
2
(
a
−
d
)
+ · · · +
(
a
−
d
)
k
−
1
]
Summing up the equalities from
d
=
1 to
d
=
a
−
1
2
implies that
p
divides
1
k
+
2
k
+ · · · +
(
a
−
1
)
k
, as claimed.
Problem 1.1.3.
Prove that
3
4
5
+
4
5
6
is a product of two integers each of which is larger than
10
2002
.
Solution.
Write 3
4
5
+
4
5
6
as
m
4
+
4
n
4
, where
n
=
2
(
5
6
−
1
)/
2
. Then the desired
factorization is
m
4
+
4
n
4
=
(
m
2
+
2
n
2
)
2
−
4
m
2
n
2
=
(
m
2
−
2
mn
+
2
n
2
)(
m
2
+
2
mn
+
2
n
2
).
Since the smaller factor is
m
2
−
2
mn
+
2
n
2
=
(
m
−
n
)
2
+
n
2
≥
n
2
=
2
5
6
−
1
>
2
8008
=
(
2
4
)
2002
>
10
2002
,
we are done.
Problem 1.1.4.
Find all positive integers n such that for all odd integers a, if
a
2
≤
n then a
|
n.
Solution.
Consider a fixed positive integer
n
. Let
a
be the greatest odd integer
such that
a
2
<
n
and hence
n
≤
(
a
+
2
)
2
. If
a
≥
7, then
a
−
4
,
a
−
2
,
a
are odd integers that divide
n
. Note that any two of these numbers are relatively
6
Do'stlaringiz bilan baham: |
