|
II Solutions, 7. More on Divisibility
Solution.
(All congruences in this problem are modulo 13.) We claim that
12
x
=
0
x
k
≡
0 for 0
≤
k
<
12
.
The case
k
=
0 is obvious, so suppose
k
>
0.
Note that the twelve powers 1
,
2
,
4
, . . . ,
2
11
represent all twelve nonzero resi-
dues mod 13. Thus 2
k
≡
1
(
mod 13
)
if and only if 12
|
k
. Since the numbers
2
,
4
, . . .
, 24 are congruent (in some order) to 1
,
2
, . . . ,
12
(
mod 13
)
, we have
12
x
=
0
x
k
≡
12
x
=
0
(
2
x
)
k
=
2
k
12
x
=
0
x
k
;
since
g
k
≡
1, we must have
"
12
x
=
0
x
k
≡
0. This proves our claim.
Now let
S
= {
(
x
1
, . . . ,
x
n
)
|
0
≤
x
i
≤
12
}
. It suffices to show that the number
of
n
-tuples
(
x
1
, . . . ,
x
n
)
∈
S
with
f
(
x
1
, . . . ,
x
n
)
≡
0 is divisible by 13, since
|
S
| =
13
n
is divisible by 13. Consider the sum
(
x
1
,...,
x
n
)
∈
S
(
f
(
x
1
, . . . ,
x
n
))
12
.
This sum counts mod 13 the number of
n
-tuples
(
x
1
, . . . ,
x
n
)
∈
S
such that
f
(
x
1
, . . . ,
x
n
)
≡
0, since by Fermat’s little theorem,
(
f
(
x
1
, . . . ,
x
n
))
12
≡
1
,
if
f
(
x
1
, . . . ,
x
n
)
≡
0
,
0
,
if
f
(
x
1
, . . . ,
x
n
)
≡
0
.
On the other hand, we can expand
(
f
(
x
1
, . . . ,
x
n
))
12
in the form
(
f
(
x
1
, . . . ,
x
n
))
12
=
N
j
=
1
c
j
n
i
=
1
x
e
j i
i
for some integers
N
,
c
j
,
e
j i
. Since
f
is a polynomial of total degree less than
n
,
we have
e
j
1
+
e
j
2
+ · · · +
e
j n
<
12
n
for every
j
, so for each
j
there exists an
i
such that
e
j i
<
12. Thus by our claim,
(
x
1
,...,
x
n
)
∈
S
c
j
n
i
=
1
x
e
j i
i
=
c
j
n
i
=
1
12
x
=
0
x
e
j i
i
≡
0
,
since one of the sums in the product is 0. Therefore
(
x
1
,...,
x
n
)
∈
S
(
f
(
x
1
, . . . ,
x
n
))
12
=
(
x
1
,...,
x
n
)
∈
S
N
j
=
1
c
j
n
i
=
1
x
e
j i
i
≡
0
,
so the number of
(
x
1
, . . . ,
x
n
)
such that
f
(
x
1
, . . . ,
x
n
)
≡
0
(
mod 13
)
is divisible
by 13, and we are done.
7.1. Congruences Modulo a Prime: Fermat’s Little Theorem
301
Problem 7.1.13.
Find all pairs
(
m
,
n
)
of positive integers, with m
,
n
≥
2
, such
that a
n
−
1
is divisible by m for each a
∈ {
1
,
2
, . . . ,
n
}
.
(2001 Romanian International Mathematical Olympiad Team Selection Test)
Solution.
The solution is the set of all
(
p
,
p
−
1
)
, for odd primes
p
. The fact that
all of these pairs are indeed solutions follows immediately from Fermat’s little
theorem. Now we show that no other solutions exist.
Suppose that
(
m
,
n
)
is a solution. Let
p
be a prime dividing
m
. We first observe
that
p
>
n
. Otherwise, we could take
a
=
p
, and then
p
n
−
1 would not be
divisible by
p
, let alone
m
. Then because
n
≥
2, we have
p
≥
3, and hence
p
is
odd.
Now we prove that
p
<
n
+
2. Suppose to the contrary that
p
≥
n
+
2. If
n
is odd, then
n
+
1 is even and less than
p
. Otherwise, if
n
is even, then
n
+
2 is
even and hence less than
p
as well, because
p
is odd. In either case, there exists
an even
d
such that
n
<
d
<
p
with
d
2
≤
n
. Setting
a
=
2 and
a
=
d
2
in the given
condition, we find that
d
n
≡
2
n
d
2
n
≡
1
·
1
≡
1
(
mod
m
),
so that
d
n
−
1
≡
0
(
mod
m
)
as well. Because
n
<
d
<
p
<
m
, we see that
1
,
2
, . . . ,
n
,
d
are
n
+
1 distinct roots of the polynomial congruence
x
n
−
1
≡
0
(
mod
p
)
. By Lagrange’s theorem, however, this congruence can have at most
n
roots, a contradiction.
Thus, we have sandwiched
p
between
n
and
n
+
2, and the only possibility is
that
p
=
n
+
1. Therefore, all solutions are of the form
(
p
k
,
p
−
1
)
with
p
an odd
prime. It remains to prove that
k
=
1. Using
a
=
n
=
p
−
1, it suffices to prove
that
p
k
((
p
−
1
)
p
−
1
−
1
).
Expanding the term
(
p
−
1
)
p
−
1
modulo
p
2
, and recalling that
p
is odd, we
have
(
p
−
1
)
p
−
1
=
p
−
1
i
=
0
p
−
1
i
(
−
1
)
p
−
1
−
i
p
i
≡
p
−
1
0
(
−
1
)
p
−
1
+
p
−
1
1
(
−
1
)
p
−
2
p
≡
1
−
p
(
p
−
1
)
≡
p
+
1
≡
1
(
mod
p
2
).
It follows immediately that
k
cannot be greater than 1, completing the proof.
302
II Solutions, 7. More on Divisibility
Problem 7.1.14.
Let p be a prime and b
0
an integer,
0
<
b
0
<
p. Prove that
there exists a unique sequence of base- p digits b
0
,
b
1
,
b
2
, . . . ,
b
n
, . . .
with the
following property: If the base- p representation of a number x ends in the group
of digits b
n
b
n
−
1
. . .
b
1
b
0
, then so does the representation of x
p
.
Solution.
We are looking for a sequence
b
0
,
b
1
,
b
2
, . . . ,
b
n
, . . .
of base
p
digits
such that the numbers
x
n
=
b
0
+
b
1
p
+ · · · +
b
n
p
n
and
x
p
n
are congruent mod-
ulo
p
n
+
1
for each
n
=
0
,
1
,
2
, . . .
Of course, the choice of the first term
b
0
is
predetermined, and given in the problem statement; let us note that the numbers
x
0
=
b
0
and
x
p
0
are congruent modulo
p
by Fermat’s little theorem. Suppose that
the base
p
digits
b
1
,
b
2
, . . . ,
b
n
are already chosen in such a way that
x
p
n
≡
x
n
(
mod
p
n
+
1
)
. We shall prove that there is a unique digit
b
n
+
1
such that
(
x
n
+
b
n
+
1
p
n
+
1
)
p
≡
x
n
+
b
n
+
1
p
n
+
1
(
mod
p
n
+
2
)
;
this proves the existence and the uniqueness at the same time. Since
(
x
n
+
b
n
+
1
p
n
+
1
)
p
=
x
p
n
+
p
1
x
p
−
1
n
b
n
+
1
p
n
+
1
+
C p
n
+
2
for some integer constant
C
, and since
p
1
is divisible by
p
, we get
(
x
n
+
b
n
+
1
p
n
+
1
)
p
≡
x
p
n
(
mod
p
n
+
2
).
Hence
b
n
+
1
should satisfy the congruence
x
p
n
−
x
n
−
b
n
+
1
p
n
+
1
≡
0
(
mod
p
n
+
2
).
(
1
)
By the induction hypothesis, the number
x
p
n
−
x
n
is divisible by
p
n
+
1
. This
implies that its
(
n
+
2
)
nd base
p
digit (from right to left) is indeed the only choice
for
b
n
+
1
such that (1) holds. The inductive proof is complete.
Problem 7.1.15.
Determine all integers n
>
1
such that
2
n
+
1
n
2
is an integer.
(31st International Mathematical Olympiad)
Solution.
We will prove that the problem has only the solution
n
=
3. First,
observe that
n
is an odd number. Then, we prove that 3
|
n
.
Let
p
be the least prime divisor of
n
. Since
n
2
|
2
n
+
1
,
2
n
+
1
≡
0
(
mod
p
)
and 2
2
n
≡
1
(
mod
p
)
. By Fermat’s little theorem, 2
p
−
1
≡
1
(
mod
p
)
. Then
2
d
≡
1
(
mod
p
)
, where
d
=
gcd
(
p
−
1
,
2
n
)
. By the definition of
p
,
d
has no
prime divisor greater than 2, which shows that
d
=
2. It follows that
p
=
3.
Let
n
=
3
k
m
, where
k
≥
1 and
(
3
,
m
)
=
1. Using the identity
x
3
k
+
1
=
(
x
+
1
)(
x
2
−
x
+
1
)(
x
2
·
3
−
x
3
+
1
)
· · ·
(
x
2
·
3
k
−
1
−
x
3
k
−
1
+
1
)
Do'stlaringiz bilan baham: |
