|
1.5
Modular Arithmetic
Problem 1.5.7.
Find all integers n
>
1
such that every prime divisor of n
6
−
1
is
a divisor of
(
n
3
−
1
)(
n
2
−
1
)
.
(2002 Baltic Mathematics Competition)
Solution.
We show that
n
=
2 is the only such integer. It is clear that
n
=
2
satisfies the conditions. For
n
>
2, write
n
6
−
1
=
(
n
3
−
1
)(
n
3
+
1
)
=
(
n
3
−
1
)(
n
+
1
)(
n
2
−
n
+
1
)
;
hence, all prime factors of
n
2
−
n
+
1 must divide
n
3
−
1 or
n
2
−
1
=
(
n
−
1
)(
n
+
1
)
.
Note, however, that
(
n
2
−
n
+
1
,
n
3
−
1
)
≤
(
n
3
+
1
,
n
3
−
1
)
≤
2; on the other hand,
n
2
−
n
+
1
=
n
(
n
−
1
)
+
1 is odd, so all prime factors of
n
2
−
n
+
1 must divide
n
+
1. But
n
2
−
n
+
1
=
(
n
+
1
)(
n
−
2
)
+
3, so we must have
n
2
−
n
+
1
=
3
k
for some
k
. Because
n
>
2, we have
k
≥
2. Now 3
|
(
n
2
−
n
+
1
)
gives
n
≡
2
(
mod 3
)
; but for each of the cases
n
≡
2
,
5
,
8
(
mod 9
)
, we have
n
2
−
n
+
1
≡
3
(
mod 9
)
, a contradiction.
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)
Solution.
We will prove the recursion
f
(
n
)
=
f
(
n
−
1
)
+
f
(
n
−
3
)
+
1 for
n
≥
4
as follows:
Call such a permutation “special.” Suppose
a
2
=
2. Then the sequence
b
i
=
a
i
+
1
−
1, 1
≤
i
≤
n
−
1, is a special permutation of 1
, . . . ,
n
−
1. Conversely, if
b
i
is special permutation of 1
, . . . ,
n
−
1, then defining
a
1
=
1 and
a
i
=
b
i
−
1
+
1
for 2
≤
i
≤
n
gives a special permutation of 1
, . . . ,
n
. Thus the number of these
is
f
(
n
−
1
)
.
If
a
2
=
2, then
a
2
=
3. Suppose
a
3
=
2; hence
a
4
=
4. Then the sequence
b
i
=
a
i
+
3
−
3 is a special permutation of 1
, . . . ,
n
−
3. As above, the converse
also holds. Hence the number of these is
f
(
n
−
3
)
.
234
II Solutions, 1. Divisibility
If
a
2
=
3 and
a
3
=
2, look at which
i
, 4
≤
i
≤
n
, has
a
i
=
2. Since
|
a
i
−
1
−
a
i
| ≤
2 and 1 and 3 are already used as
a
1
and
a
2
, we must have
a
i
−
1
=
4.
However, if
i
=
n
, the same argument shows that
a
i
+
1
=
4, a contradiction. Thus
a
n
=
2 and
a
n
−
1
=
4. Hence
a
3
=
5, and iterating this argument shows that
the only such permutation is 1
,
3
,
5
, . . . ,
6
,
4
,
2 with all the odd numbers in order
followed by the even numbers in reverse order. Thus there is exactly one special
permutation of this form.
Combining these three cases, we see that
f
(
n
)
=
f
(
n
−
1
)
+
f
(
n
−
3
)
+
1
for
n
≥
4. Calculating shows that
f
(
n
) (
mod 3
)
is
f
(
1
)
=
1, 1, 2, 1, 0, 0, 2,
0, 1, 1, 2, 1,
. . .
, repeating with period 8. Since 1996
≡
4
(
mod 8
)
, we have
f
(
1996
)
≡
f
(
4
)
=
4
(
mod 3
)
, so
f
(
1996
)
is not divisible by 3.
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)
Solution.
Since
2
kn
+
d
−
1
≡
2
d
−
1
(
mod 2
n
−
1
),
we have that 2
m
−
1 divides 2
n
−
1 if and only if
m
divides
n
. Thus in either case,
we must have
n
=
km
, in which case
2
km
−
1
2
m
−
1
=
1
+
2
m
+ · · · +
2
m
(
k
−
1
)
≡
k
(
mod 2
m
−
1
).
The two conditions are now that
k
is divisible by 2
m
−
1 and that
n
is divisible
by
m
(
2
m
−
1
)
, which are equivalent.
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)
Solution.
The answer is
n
=
130. Note that
x
2
≡
0
(
mod 4
)
when
x
is even and
that
x
2
≡
1
(
mod 4
)
when
x
is odd.
If
n
is odd, then all the
d
i
are odd and
n
≡
d
2
1
+
d
2
2
+
d
2
3
+
d
2
4
≡
1
+
1
+
1
+
1
≡
0
(
mod 4
)
, a contradiction. Thus, 2
|
n
.
If 4
|
n
then
d
1
=
1 and
d
2
=
2, and
n
≡
1
+
0
+
d
2
3
+
d
2
4
≡
0
(
mod 4
)
, a
contradiction. Thus, 4
n
.
Therefore
{
d
1
,
d
2
,
d
3
,
d
4
} = {
1
,
2
,
p
,
q
}
or
{
1
,
2
,
p
,
2
p
}
for some odd primes
p
,
q
. In the first case,
n
≡
3
(
mod 4
)
, a contradiction. Thus
n
=
5
(
1
+
p
2
)
and
5
|
n
, so
p
=
d
3
=
5 and
n
=
130.
1.5. Modular Arithmetic
235
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)
Solution.
Denote the sum in question by
S
. Combine the first summand with the
last, the second one with the next-to-last, and so on, to get
2
S
=
(
r
1
+
r
p
−
1
)
+
(
r
2
+
r
p
−
2
)
+ · · · +
(
r
p
−
1
+
r
1
).
(
1
)
We have
r
i
+
r
p
−
i
≡
i
p
+
(
p
−
i
)
p
(
mod
p
2
)
by the definition of the numbers
r
1
,
r
2
, . . . ,
r
p
−
1
. Furthermore, because
p
is odd,
i
p
+
(
p
−
i
)
p
=
p
p
−
p
1
p
p
−
1
i
+
p
2
p
p
−
2
i
2
− · · · +
p
p
−
1
pi
p
−
1
.
Since
p
is a prime, each binomial coefficient above is divisible by
p
, which
yields the conclusion that
r
i
+
r
p
−
i
is divisible by
p
2
. But 0
<
r
i
<
p
2
, 0
<
r
p
−
i
<
p
2
, because
p
is a prime (so neither one equals 0), and now we may claim
that
r
i
+
r
p
−
i
=
p
2
for
i
=
1
,
2
, . . . ,
p
−
1
.
(
2
)
The equalities (1) and (2) show that
S
=
p
−
1
2
p
2
=
p
3
−
p
2
2
.
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)
Solution.
There are four such integers. With congruences all taken modulo 1997,
we have
x
2
+
(
x
+
1
)
2
≡
2
x
2
+
2
x
+
1
≡
4
x
2
+
4
x
+
2
≡
0
,
i.e.,
(
2
x
+
1
)
2
≡ −
1. Since 1997 is a prime of the form 4
k
+
1, there are exactly two
distinct solutions to
u
2
≡ −
1 (see Section 9.1 for more details). Each corresponds
to a different solution to
(
2
x
+
1
)
2
≡ −
1.
Also, the two solutions to
(
2
x
+
1
)
2
≡ −
1 are nonzero, since 0 does not
satisfy the equation. Therefore, there are exactly two satisfactory integers
x
from
−
1997 to
−
1 and two more from 1 to 1997, for a total of four integer solutions,
as claimed.
236
Do'stlaringiz bilan baham: |
