|
1.5. Modular Arithmetic
33
Additional Problems
Problem 1.5.7.
Find all integers
n
>
1 such that any prime divisor of
n
6
−
1 is a
divisor of
(
n
3
−
1
)(
n
2
−
1
)
.
(2002 Baltic Mathematics Competition)
Problem 1.5.8.
Let
f
(
n
)
be the number of permutations
a
1
, . . . ,
a
n
of the integers
1
, . . . ,
n
such that
(i)
a
1
=
1;
(ii)
|
a
i
−
a
i
+
1
| ≤
2
,
i
=
1
, . . . ,
n
−
1.
Determine whether
f
(
1996
)
is divisible by 3.
(1996 Canadian Mathematical Olympiad)
Problem 1.5.9.
For natural numbers
m
,
n
, show that 2
n
−
1 is divisible by
(
2
m
−
1
)
2
if and only if
n
is divisible by
m
(
2
m
−
1
)
.
(1997 Russian Mathematical Olympiad)
Problem 1.5.10.
Suppose that
n
is a positive integer and let
d
1
<
d
2
<
d
3
<
d
4
be the four smallest positive integer divisors of
n
. Find all integers
n
such that
n
=
d
2
1
+
d
2
2
+
d
2
3
+
d
2
4
.
(1999 Iranian Mathematical Olympiad)
Problem 1.5.11.
Let
p
be an odd prime. For each
i
=
1
,
2
, . . . ,
p
−
1 denote by
r
i
the remainder when
i
p
is divided by
p
2
. Evaluate the sum
r
1
+
r
2
+ · · · +
r
p
−
1
.
(Kvant)
Problem 1.5.12.
Find the number of integers
x
with
|
x
| ≤
1997 such that 1997
divides
x
2
+
(
x
+
1
)
2
.
(1998 Indian Mathematical Olympiad)
Problem 1.5.13.
Find the greatest common divisor of the numbers
A
n
=
2
3
n
+
3
6
n
+
2
+
5
6
n
+
2
when
n
=
0
,
1
, . . . ,
1999.
(1999 Junior Balkan Mathematical Olympiad)
34
I Fundamentals, 1. Divisibility
1.6
Chinese Remainder Theorem
There are many situations in which one wishes to solve a congruence equation
f
(
x
)
≡
a
(
mod
N
)
for some large
N
. Suppose we factor
N
as
N
=
p
k
1
1
p
k
2
2
· · ·
p
k
r
r
. Then any solution must also have
f
(
x
)
≡
a
(
mod
p
k
i
i
)
for all
i
. Conversely,
if
f
(
x
)
≡
a
(
mod
p
k
i
u
)
, then all the
p
k
i
i
divide
f
(
x
)
−
a
. Hence their least com-
mon multiple
N
divides
f
(
x
)
−
a
. Thus one congruence mod a very large
N
is
equivalent to lots of congruences mod its prime power factors. These congruences
are often much easier to solve, either because
p
k
i
i
is much smaller than
N
, or be-
cause of special facts about primes such as Fermat’s little theorem. Thus it might
be easier to solve
f
(
x
)
≡
a
(
mod
p
k
i
i
)
for all
i
. However, this solution will often
give us a list of congruences that
x
must satisfy, say
x
≡
c
1
(
mod
m
1
), . . . ,
x
≡
c
n
(
mod
m
n
).
This leaves us with the problem whether such a system has a solution and how to
find the solutions. In solving systems of this form an important part is played by
the following very important result:
Theorem 1.6.1.
(Chinese remainder theorem)
Let m
1
,
· · ·
,
m
n
be positive inte-
gers different from
1
and pairwise relatively prime. Then for any nonzero integers
a
1
, . . . ,
a
r
the system of linear congruences
x
≡
a
1
(
mod
m
1
), . . . ,
x
≡
a
r
(
mod
m
r
)
has solutions, and any two such solutions are congruent modulo m
=
m
1
· · ·
m
r
.
Proof.
It is clear that gcd
m
m
j
,
m
j
=
1,
j
=
1
, . . . ,
r
. Applying Proposition
1.3.1, it follows that there is an integer
b
j
such that
m
m
j
b
j
≡
1
(
mod
m
j
),
j
=
1
, . . . ,
r
.
Then
m
m
j
b
j
a
j
≡
a
j
(
mod
m
j
),
j
=
1
, . . . ,
r
.
Now consider the integer
x
0
=
r
j
=
1
m
m
j
b
j
a
j
.
We have
x
0
≡
r
j
=
1
m
m
j
b
j
a
j
(
mod
m
i
)
≡
m
m
i
b
i
a
i
(
mod
m
i
)
≡
a
i
(
mod
m
i
),
i
=
1
, . . . ,
r
,
1.6. Chinese Remainder Theorem
35
that is,
x
0
is a solution to the system of linear congruences.
If
x
1
is another solution, then
x
1
≡
x
0
(
mod
m
i
)
,
i
=
1
, . . . ,
r
. Applying
property (8) in Section 1.5, the conclusion follows.
Example.
Let us find the solutions to the system of linear congruences
x
≡
2
(
mod 3
),
x
≡
1
(
mod 4
),
x
≡
3
(
mod 5
).
We proceed as in the proof of the theorem. Because in this case
m
=
3
·
4
·
5
=
60, we have to find a solution to each of the congruences
60
3
b
1
≡
1
(
mod 3
),
60
4
b
2
≡
1
(
mod 4
),
60
5
b
3
≡
1
(
mod 5
).
This is equivalent to finding solutions to the congruences
2
b
1
≡
1
(
mod 3
),
3
b
2
≡
1
(
mod 4
),
2
b
3
≡
1
(
mod 5
).
We obtain
b
1
=
2,
b
2
=
3,
b
3
=
3. Then
x
0
=
20
·
2
·
2
+
15
·
3
·
1
+
12
·
3
·
3
=
233
.
Taking into account that all solutions are congruent modulo 60, it follows that
it suffices to take
x
0
=
53. All solutions are given by
x
=
53
+
60
k
,
k
∈
Z
.
Problem 1.6.1.
We call a lattice point X in the plane visible from the origin O if
the segment O X does not contain any other lattice points besides O and X . Show
that for any positive integer n, there exists a square of n
2
lattice points (with sides
parallel to the coordinate axes) such that none of the lattice points inside the
square is visible from the origin.
(2002 Taiwanese Mathematical Olympiad)
Solution.
Suppose that the lower-left lattice point of such a square has coordinates
(
x
1
,
y
1
)
. We shall show that it is possible to select
(
x
1
,
y
1
)
such that the square
of lattice points with
(
x
1
,
y
1
)
at its corner and
n
points on a side contains only
invisible points. This can be accomplished by ensuring that each point has both
coordinates divisible by some prime number; this would imply that by dividing
both coordinates by this prime, we could find another lattice point that is between
the origin and this point.
In fact, we note that a lattice point
X
=
(
x
,
y
)
is visible from the origin if and
only if gcd
(
x
,
y
)
=
1.
Select
n
2
distinct prime numbers and call them
p
i
,
j
, 1
≤
1
,
j
≤
n
. Now find
x
1
satisfying the following congruences:
x
1
≡
0
(
mod
p
1
,
1
p
1
,
2
· · ·
p
1
,
n
),
x
1
+
1
≡
0
(
mod
p
2
,
1
p
2
,
2
· · ·
p
2
,
n
),
. . .
x
1
+
n
−
1
≡
0
(
mod
p
n
,
1
p
n
,
2
· · ·
p
n
,
n
).
36
I Fundamentals, 1. Divisibility
Likewise select
y
1
satisfying
y
1
≡
0
(
mod
p
1
,
1
p
2
,
1
· · ·
p
n
,
1
),
y
1
+
1
≡
0
(
mod
p
1
,
2
p
2
,
2
· · ·
p
n
,
2
),
. . .
y
1
+
n
−
1
≡
0
(
mod
p
1
,
n
p
2
,
n
· · ·
p
n
,
n
).
Both values must exist by the Chinese remainder theorem. Thus we have
proved that it is possible to determine a position for
(
x
1
,
y
1
)
such that every point
in the square of
n
2
lattice points with
(
x
1
,
y
1
)
at its lower left corner is associated
with some prime by which both of its coordinates are divisible; thus no points in
this square are visible from the origin.
Problem 1.6.2.
Show that there exists an increasing sequence
{
a
n
}
∞
n
=
1
of natural
numbers such that for any k
≥
0
, the sequence
{
k
+
a
n
}
contains only finitely
many primes.
(1997 Czech and Slovak Mathematical Olympiad)
Solution.
Let
p
k
be the
k
th prime number,
k
≥
1. Set
a
1
=
2. For
n
≥
1, let
a
n
+
1
be the least integer greater than
a
n
that is congruent to
−
k
modulo
p
k
+
1
for
all
k
≤
n
. Such an integer exists by the Chinese remainder theorem. Thus, for all
k
≥
0,
k
+
a
n
≡
0
(
mod
p
k
+
1
)
for
n
≥
k
+
1. Then at most
k
+
1 values in the
sequence
{
k
+
a
n
}
can be prime; from the (
k
+
2)th term onward, the values are
nontrivial multiples of
p
k
+
1
and must be composite. This completes the proof.
Additional Problems
Problem 1.6.3.
Let
P
(
x
)
be a polynomial with integer coefficients. Suppose that
the integers
a
1
,
a
2
, . . . ,
a
n
have the following property: For any integer
x
there
exists an
i
∈ {
1
,
2
, . . . ,
n
}
such that
P
(
x
)
is divisible by
a
i
. Prove that there is an
i
0
∈ {
1
,
2
, . . . ,
n
}
such that
a
i
0
divides
P
(
x
)
for every integer
x
.
(St. Petersburg City Mathematical Olympiad)
Problem 1.6.4.
For any set of positive integers
{
a
1
,
a
2
, . . . ,
a
n
}
there exists a
positive integer
b
such that the set
{
ba
1
,
ba
2
, . . . ,
ba
n
}
consists of perfect powers.
Do'stlaringiz bilan baham: |
