|
I Fundamentals, 1. Divisibility
Let us prove the last property. From
a
≡
b
(
mod
m
i
)
,
i
=
1
, . . . ,
k
, it follows
that
m
i
|
a
−
b
,
i
=
1
, . . . ,
k
. Hence
a
−
b
is a common multiple of
m
1
, . . . ,
m
k
,
and so lcm
(
m
1
, . . . ,
m
k
)
|
a
−
b
. That is,
a
≡
b
(
mod lcm
(
m
1
, . . . ,
m
k
))
. Con-
versely, from
a
≡
b
(
mod lcm
(
m
1
, . . . ,
m
k
))
, and the fact that each
m
i
divides
lcm
(
m
1
, . . . ,
m
k
)
we obtain
a
≡
b
(
mod
m
i
)
,
i
=
1
, . . . ,
k
.
Theorem 1.5.1.
Let a
,
b
,
n be integers, n
=
0
, such that a
=
nq
1
+
r
1
, b
=
nq
2
+
r
2
,
0
≤
r
1
,
r
2
<
|
n
|
. Then a
≡
b
(
mod
n
)
if and only if r
1
=
r
2
.
Proof.
Because
a
−
b
=
n
(
q
1
−
q
2
)
+
(
r
1
−
r
2
)
, it follows that
n
|
a
−
b
if and
only if
n
|
r
1
−
r
2
. Taking into account that
|
r
1
−
r
2
|
<
|
n
|
, we have
n
|
r
1
−
r
2
if
and only if
r
1
=
r
2
.
Problem 1.5.1.
For all the positive integers k
≤
1999
, let S
1
(
k
)
be the sum of all
the remainders of the numbers
1
,
2
, . . . ,
k when divided by
4
, and let S
2
(
k
)
be the
sum of all the remainders of the numbers k
+
1
,
k
+
2
, . . . ,
2000
when divided by
3
. Prove that there is a unique positive integer m
≤
1999
so that S
1
(
m
)
=
S
2
(
m
)
.
(1999 Romanian Mathematical Olympiad)
Solution.
Let
A
k
= {
1
,
2
,
3
, . . . ,
k
}
and
B
k
= {
k
+
1
,
k
+
2
, . . . ,
2000
}
. From the
division of integers we have
k
=
4
q
1
+
r
1
,
with
r
1
∈ {
0
,
1
,
2
,
3
}
.
(
1
)
If
s
1
(
k
)
is the sum of the remainders after division by 4 of the last
r
1
elements
of
A
k
, then let
S
1
(
k
)
=
6
q
1
+
s
1
(
k
),
with 0
≤
s
1
(
k
)
≤
6
.
(
2
)
If
r
1
=
0, then set
s
1
(
k
)
=
0.
Using again the division of integers, there exist integers
q
2
,
r
2
such that
2000
−
k
=
3
q
2
+
r
2
,
with
r
2
∈ {
0
,
1
,
2
}
.
(
3
)
If
s
2
(
k
)
is the sum of the remainders on division by 3 of the last
r
2
elements
of
B
k
, then let
s
2
(
k
)
=
3
q
2
+
s
2
(
k
),
with 0
≤
s
2
(
k
)
≤
3
.
(
4
)
Again we set
S
2
(
k
)
=
0 if
r
2
=
0.
Since
S
1
(
k
)
=
S
2
(
k
)
,
s
2
(
k
)
−
s
1
(
k
)
=
3
(
2
q
1
−
q
2
)
, so 3
|
2
q
1
−
q
2
| = |
s
2
(
k
)
−
s
1
(
k
)
| ≤
6, and
|
2
q
1
−
q
2
| ≤
2. In other words,
|
2
q
1
−
q
2
| ∈ {
0
,
1
,
2
}
.
If 2
q
1
=
q
2
, then (1) and (3) imply 2000
−
(
r
1
+
r
2
)
=
10
q
1
; hence 10
|
(
r
1
+
r
2
)
. Then
r
1
=
r
2
=
0 and
q
1
=
200. From (1) it follows that
k
=
800, and
from (2) and (4) we have
S
1
(
800
)
=
S
2
(
800
)
=
1200.
Furthermore,
S
1
(
k
)
≤
S
1
(
k
+
1
)
, and
S
2
(
k
)
≥
S
2
(
k
+
1
)
for all
k
∈ {
1
,
2
, . . .
,
1998
}
. Since
S
1
(
799
)
=
S
1
(
800
)
and
S
2
(
799
)
=
S
2
(
800
)
+
2
>
S
1
(
800
)
, we
1.5. Modular Arithmetic
31
deduce that
S
1
(
k
) <
S
2
(
k
)
for all
k
∈ {
1
,
2
, . . . ,
799
}
. Since
S
1
(
801
)
=
S
1
(
800
)
+
1
>
S
2
(
800
)
≥
S
2
(
801
)
, we derive that
S
1
(
k
) >
S
2
(
k
)
for all
k
∈ {
801
,
802
, . . .
,
1999
}
. Consequently,
S
1
(
m
)
=
S
2
(
m
)
if and only if
m
=
800.
Problem 1.5.2.
Let n be a positive integer. Show that if a and b are integers
greater than
1
such that
2
n
−
1
=
ab, then ab
−
(
a
−
b
)
−
1
can be written as
k
·
2
2
m
for some odd integer k and some positive integer m.
(2001 Balkan Mathematical Olympiad)
Solution.
Note that
ab
−
(
a
−
b
)
−
1
=
(
a
+
1
)(
b
−
1
)
. We shall show that the
highest powers of 2 dividing
(
a
+
1
)
and
(
b
−
1
)
are the same. Let 2
s
and 2
t
be the highest powers of 2 dividing
(
a
+
1
)
and
(
b
−
1
)
, respectively. Because
a
+
1
,
b
−
1
≤
ab
+
1
=
2
n
, we have
s
,
t
≤
n
.
Note that 2
s
divides 2
n
=
ab
+
1 and
a
+
1, so that
ab
≡
a
≡ −
1
(
mod 2
s
).
Hence,
b
≡
1
(
mod 2
s
)
, or 2
s
|
b
−
1, so that
s
≤
t
.
Similarly,
ab
≡ −
b
≡ −
1
(
mod 2
t
)
, so
a
≡ −
1
(
mod 2
t
)
, and 2
t
|
a
+
1.
Thus,
t
≤
s
.
Therefore,
s
=
t
, the highest power of 2 dividing
(
a
+
1
)(
b
−
1
)
is 2
s
, and
ab
−
(
a
−
b
)
−
1
=
k
·
2
2
s
for some odd
k
.
Problem 1.5.3.
Find all nonnegative integers m such that
(
2
2
m
+
1
)
2
+
1
is divisible
by at most two different primes.
(2002 Baltic Mathematics Competition)
Solution.
We claim
m
=
0
,
1
,
2 are the only such integers. It is easy to check that
these values of
m
satisfy the requirement. Suppose some
m
≥
3 works. Write
(
2
2
m
+
1
)
2
+
1
=
(
2
2
m
+
1
+
1
)
2
−
2
·
2
2
m
+
1
=
(
2
2
m
+
1
+
2
m
+
1
+
1
)(
2
2
m
+
1
−
2
m
+
1
+
1
).
The two factors are both odd, and their difference is 2
m
+
2
; hence, they are rel-
atively prime. It follows that each is a prime power. We also know that
(
2
2
m
+
1
)
2
=
4
2
m
+
1
≡ −
1
(
mod 5
)
, so one of the factors 2
2
m
+
1
±
2
m
+
1
+
1 must be a power
of 5. Let 2
2
m
+
1
+
2
m
+
1
s
+
1
=
5
k
, where
s
= ±
1 is the appropriate sign.
Taking the above equation modulo 8, and using the assumption
m
≥
3, we
obtain 5
k
≡
1
(
mod 8
)
, so that
k
is even. Writing
k
=
2
l
, we have
2
m
+
1
(
2
m
+
s
)
=
(
5
l
−
1
)(
5
l
+
1
).
The factor 5
l
+
1 is congruent to 2
(
mod 4
)
, so 5
l
−
1
=
2
m
a
for some odd
integer
a
. But if
a
=
1, then
2
=
(
5
l
+
1
)
−
(
5
l
−
1
)
=
2
(
2
m
+
s
)
−
2
m
=
2
m
+
2
s
≥
2
3
−
2
,
32
Do'stlaringiz bilan baham: |
