|
II Solutions, 7. More on Divisibility
It is easy to show that for any integer
x
,
x
2
+
1 is not divisible by 4. Then, by
the above decomposition,
a
2
m
−
1 is divisible by 2
s
+
m
and it is not divisible by
2
s
+
m
+
1
. Hence, the required number is 2
2000
−
s
.
Assume that
a
≡ −
1
(
mod 2
s
)
and
a
≡ −
1
(
mod 2
s
+
1
)
, where
s
≥
2.
Equivalently,
a
has the binary representation
a
=
1
. . .
0 11
. . .
1
s
digits
.
As before,
a
−
1 is divisible by 2 and not divisible by 2
2
, and
a
2
k
+
1 is divisible
by 2 and not divisible by 2
2
, for all
k
≥
1. From the above decomposition,
a
2
m
−
1
is divisible by 2
s
+
m
and not divisible by 2
s
+
m
+
1
. Hence, in this case, the required
exponent is
n
=
2
2000
−
s
when
s
≤
1999, and
n
=
2 when
s
≥
2000.
Problem 7.2.7.
Let n
=
p
r
1
1
· · ·
p
r
k
k
be the prime factorization of the positive
integer n and let r
≥
2
be an integer. Prove that the following are equivalent:
(a) The equation x
r
≡
a
(
mod
n
)
has a solution for every a.
(b) r
1
=
r
2
= · · · =
r
k
=
1
and
gcd
(
p
i
−
1
,
r
)
=
1
for every i
∈ {
1
,
2
, . . . ,
k
}
.
(1995 UNESCO Mathematical Contest)
Solution.
If (b) holds, then
ϕ(
n
)
=
(
p
1
−
1
)
· · ·
(
p
k
−
1
)
is coprime to
r
; thus there
exists
s
with
r s
≡
1
(
mod
φ(
n
))
, and the unique solution of
x
r
≡
a
(
mod
n
)
is
x
≡
a
s
(
mod
n
)
. Conversely, suppose
x
r
≡
a
(
mod
n
)
has a solution for every
a
; then
x
r
≡
a
(
mod
p
r
i
i
)
also has a solution for every
a
. However, if
r
i
>
1
and
a
is a number divisible by
p
but not by
p
2
, then
x
r
cannot be congruent to
a
,
since it is not divisible by
p
unless
x
is divisible by
p
, in which case it is already
divisible by
p
2
. Hence
r
1
=
1.
If
d
=
gcd
(
p
i
−
1
,
r
)
and every
a
is congruent to
x
r
for some
x
, then
a
(
p
i
−
1
)/
d
≡
1
(
mod
p
i
)
for all
a
. Hence by Lagrange’s theorem, the polynomial
P
(
t
)
=
t
(
p
i
−
1
)/
d
−
1 must have degree
p
i
−
1, that is,
d
=
1.
7.3
The Order of an Element
Problem 7.3.6.
Find all ordered triples of primes
(
p
,
q
,
r
)
such that
p
|
q
r
+
1
,
q
|
r
p
+
1
,
r
|
p
q
+
1
.
(2003 USA International Mathematical Olympiad Team Selection Test)
Solution.
It is quite clear that
p
,
q
,
r
are distinct. Indeed, if, for example,
p
=
q
,
then the relation
p
|
q
r
+
1 is impossible. We will prove that we cannot have
p
,
q
,
r
>
2. Suppose this is the case. The first condition
p
|
q
r
+
1 implies
7.3. The Order of an Element
307
p
|
q
2
r
−
1, and so
o
p
(
q
)
|
2
r
. If
o
p
(
q
)
is odd, it follows that
p
|
q
r
−
1,
which combined with
p
|
q
r
+
1 yields
p
=
2, which is impossible. Thus,
o
p
(
q
)
is either 2 or 2
r
. Could we have
o
p
(
q
)
=
2
r
? No, since this would imply that
2
r
|
p
−
1, and so 0
≡
p
q
+
1
≡
2
(
mod
r
)
, that is,
r
=
2, false. Therefore,
the only possibility is
o
p
(
q
)
=
2, and so
p
|
q
2
−
1. We cannot have
p
|
q
−
1,
because
p
|
q
r
+
1 and
p
=
2. Thus,
p
|
q
+
1 and in fact
p
|
q
+
1
2
. In the same
way, we find that
q
|
r
+
1
2
and
r
|
p
+
1
2
. This is clearly impossible, just by looking
at the largest among
p
,
q
,
r
. So, our assumption was wrong, and indeed one of the
three primes must equal 2. Suppose without loss of generality that
p
=
2. Then
q
is odd,
q
|
r
2
+
1, and
r
|
2
q
+
1. Similarly,
o
r
(
2
)
|
2
q
. If
q
|
o
r
(
2
)
, then
q
|
r
−
1,
and so
q
|
r
2
+
1
−
(
r
2
−
1
)
=
2, which contradicts the already established result
that
q
is odd. Thus,
o
r
(
2
)
|
2 and
r
|
3. As a matter of fact, this implies that
r
=
3
and
q
=
5, yielding the triple
(
2
,
5
,
3
)
. It is immediate to verify that this triple
satisfies all conditions of the problem. Moreover, all solutions are given by cyclic
permutations of the components of this triple.
Problem 7.3.7.
Find all primes p
,
q such that pq
|
2
p
+
2
q
.
Solution.
Note that
(
p
,
q
)
=
(
2
,
2
), (
2
,
3
), (
3
,
2
)
satisfy this property and let us
show that there are no other such pairs. Assume, by contradiction, that
p
=
2 and
q
=
2. Write
p
−
1
=
2
l
n
,
q
−
1
=
2
k
m
, where
m
,
n
are odd positive integers.
Because
pq
|
2
p
+
2
q
, using Fermat’s little theorem, we obtain 0
≡
2
p
+
2
q
≡
2
p
+
2
(
mod
q
)
. It follows that 2
p
−
1
≡ −
1
(
mod
q
)
. If we set
x
=
2
n
, then
we have
x
2
l
≡ −
1
(
mod
q
)
; hence
o
(
x
)
=
2
l
+
1
(since
x
2
l
+
1
≡
1
(
mod
q
)
and
x
2
l
≡
1
(
mod
q
)
). It follows that 2
l
+
1
=
o
q
(
x
)
|
ϕ(
q
)
=
q
−
1
=
2
k
m
, i.e.,
l
+
1
≤
k
.
In a similar way we can prove that
k
+
1
≤
l
, and we get
l
≤
k
−
1
≤
l
−
2, a
contradiction. Therefore, it is necessary to have
p
=
2 or
q
=
2. If, for example,
q
=
2, then
p
|
2
p
+
2
q
=
2
p
+
2
2
, 0
≡
2
p
+
2
2
≡
2
+
2
2
=
6
(
mod
p
)
, and we
get
p
∈ {
2
,
3
}
.
Problem 7.3.8.
Prove that for any integer n
≥
2
,
3
n
−
2
n
is not divisible by n.
Solution.
Assume by contradiction that
n
|
3
n
−
2
n
for some positive integer
n
.
Let us denote by
p
the smallest prime divisor of
n
. Since
n
|
3
n
−
2
n
, it follows that
p
≥
5. Consider a positive integer
a
such that 2
a
≡
1
(
mod
p
)
. From 3
n
≡
2
n
(
mod
p
)
we obtain
(
3
a
)
n
≡
1
(
mod
p
)
. Let
d
=
o
p
(
3
a
)
. It follows that
d
|
p
−
1
and
d
|
n
. But
d
<
p
and
d
|
n
implies
d
=
1, because of the minimality of
p
. We
get 3
a
≡
1
(
mod
p
)
and 2
a
≡
1
(
mod
p
)
, i.e.,
a
≡
0
(
mod
p
)
, a contradiction
to 2
a
≡
1
(
mod
p
)
.
Problem 7.3.9.
Find all positive integers m
,
n such that n
|
1
+
m
3
n
+
m
2
·
3
n
.
(Bulgarian International Mathematical Olympiad Team Selection Test)
Solution.
From
n
|
1
+
m
3
n
+
m
2
·
3
n
it follows that
n
|
m
3
n
+
1
−
1; hence
d
=
o
n
(
m
)
divides 3
n
+
1
, i.e.,
d
=
3
k
for some positive integer
k
. If
k
≤
n
, then
d
|
3
n
implies
308
Do'stlaringiz bilan baham: |
