|
Part (a) is straightforward. In fact, we will prove that any prime factor
of
f
p
(
m
)
is relatively prime to
m
(
m
−
1
)
. Take such a prime divisor
q
. Because
q
|
1
+
m
+· · ·+
m
p
−
1
, it is clear that gcd
(
q
,
m
)
=
1. Moreover, if gcd
(
q
,
m
−
1
)
=
1,
then
q
|
m
−
1, and because
q
|
1
+
m
+ · · · +
m
p
−
1
, it follows that
q
|
p
. But
p
|
m
and we find that
q
|
m
, which is clearly impossible.
More difficult is (b). But we are tempted to use (a) and to explore the proper-
ties of
f
p
(
m
)
, just as in the previous problem. So, let us take a prime
q
|
f
p
(
m
)
for
a certain positive integer
m
divisible by
p
. By part (a), gcd
(
q
,
m
−
1
)
=
1. Since
q
|
m
p
−
1, we must have
o
q
(
m
)
=
p
and hence
q
≡
1
(
mod
p
)
. Now we need to
find a sequence
(
m
k
)
k
≥
1
of multiples of
p
such that
f
p
(
m
k
)
are pairwise relatively
prime. This is not as easy as in the first example. Anyway, just by trial and error,
it is not difficult to find such a sequence. There are many other approaches, but
we like the following one: take
m
1
=
p
and
m
k
=
p f
(
m
1
)
f
p
(
m
2
)
· · ·
f
p
(
m
k
−
1
)
.
Let us prove that
f
p
(
m
k
)
is relatively prime to
f
p
(
m
1
),
f
p
(
m
2
), . . . ,
f
p
(
m
k
−
1
)
.
Fortunately, this is easy, since
f
p
(
m
1
)
f
p
(
m
2
)
· · ·
f
p
(
m
k
−
1
)
|
f
p
(
m
k
)
−
f
p
(
0
)
=
f
p
(
m
k
)
−
1. The solution ends here.
Problem 7.3.4.
Find the smallest number n with the property that
2
2005
|
17
n
−
1
.
Solution.
The problem actually asks for
o
2
2005
(
17
)
. We know that
o
2
2005
(
17
)
|
ϕ(
2
2005
)
=
2
2004
, so
o
2
2005
(
17
)
=
2
k
, where
k
∈ {
1
,
2
, . . . ,
2004
}
. The order
140
I Fundamentals, 7. More on Divisibility
of an element has done its job. Now it is time to work with exponents. We have
2
2005
|
17
2
k
−
1. Using the factorization
17
2
k
−
1
=
(
17
−
1
)(
17
+
1
)(
17
2
+
1
)
· · ·
(
17
2
k
−
1
+
1
),
we proceed by finding the exponent of 2 in each factor of this product. But this is
not difficult, because for all
i
≥
0 the number 17
2
t
+
1 is a multiple of 2, but not
a multiple of 4. Thus,
v
2
(
17
2
k
−
1
)
=
4
+
k
, and the order is found by solving the
equation
k
+
4
=
2005. Thus,
o
2
2005
(
17
)
=
2
2001
is the answer to the problem.
Problem 7.3.5.
Find all prime numbers p
,
q such that p
2
+
1
|
2003
q
+
1
and
q
2
+
1
|
2003
p
+
1
.
Solution.
Let us suppose that
p
≤
q
. We discuss first the trivial case
p
=
2. In
this case, 5
|
2003
q
+
1, and it is easy to deduce that
q
is even; hence
q
=
2,
which is a solution of the problem. Now, suppose that
p
>
2 and let
r
be a prime
factor of
p
2
+
1. Because
r
|
2003
2
q
−
1, it follows that
o
r
(
2003
)
|
2
q
. Suppose
that
(
q
,
o
r
(
2003
))
=
1. Then
o
r
(
2003
)
|
2 and
r
|
2003
2
−
1, but we cannot
have
r
|
2003
−
1, since this would give 2003
q
≡
1
(
mod
r
)
, contrary to the
hypotheses. Thus
r
|
2003
+
1
=
2
2
·
3
·
167. It seems that this is a dead end, since
there are too many possible values for
r
. Another simple observation narrows the
number of possible cases: because
r
|
p
2
+
1,
r
must be of the form 4
k
+
1 or
equal to 2, and now we do not have many possibilities:
r
∈ {
2
,
13
}
. The case
r
=
13 is also impossible, because 2003
q
+
1
≡
2
(
mod 13
)
and
r
|
2003
q
+
1.
So, we have found that for any prime factor
r
of
p
2
+
1, we have either
r
=
2
or
q
|
o
r
(
2003
)
, which in turn implies
q
|
r
−
1. Because
p
2
+
1 is even but not
divisible by 4 and because any odd prime factor of it is congruent to 1 modulo
q
,
we must have
p
2
+
1
≡
2
(
mod
q
)
. This implies that
p
2
+
1
≡
2
(
mod
q
)
, that
is,
q
|
(
p
−
1
)(
p
+
1
)
. Combining this with the assumption that
p
≤
q
yields
q
|
p
+
1 and in fact
q
=
p
+
1. It follows that
p
=
2, contradicting the assumption
p
>
2. Therefore the only pair is (2
,
2).
Additional Problems
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)
Problem 7.3.7.
Find all primes
p
,
q
such that
pq
|
2
p
+
2
q
.
Problem 7.3.8.
Prove that for any positive integer
n
≥
2, 3
n
−
2
n
is not divisible
by
n
.
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)
7.4. Wilson’s Theorem
141
Problem 7.3.10.
Let
a
,
n
>
2 be positive integers such that
n
|
a
n
−
1
−
1 and
n
does not divide any of the numbers
a
x
−
1, where
x
<
n
−
1 and
x
|
n
−
1. Prove
that
n
is a prime number.
Problem 7.3.11.
Find all prime numbers
p
,
q
for which the congruence
α
3
pq
≡
α (
mod 3
pq
)
holds for all integers
α
.
(1996 Romanian Mathematical Olympiad)
Problem 7.3.12.
Let
p
be a prime number. Prove that there exists a prime number
q
such that for every integer
n
, the number
n
p
−
p
is not divisible by
q
.
(44th International Mathematical Olympiad)
7.4
Wilson’s Theorem
Theorem 7.4.1.
(Wilson’s
1
theorem)
For any prime p, p
|
(
p
−
1
)
! +
1
.
Proof.
The property holds for
p
=
2 and
p
=
3, so we may assume that
p
≥
5. Let
S
= {
2
,
3
, . . . ,
p
−
2
}
. For any
h
in
S
, the integers
h
,
2
h
, . . . , (
p
−
1
)
h
yield distinct remainders when divided by
p
. Hence there is a unique
h
∈
{
1
,
2
, . . . ,
p
−
1
}
such that
hh
≡
1
(
mod
p
)
. Moreover,
h
=
1 and
h
=
p
−
1;
hence
h
∈
S
. In addition,
h
=
h
; otherwise,
h
2
≡
1
(
mod
p
)
, implying
p
|
h
−
1
or
p
|
h
+
1, which is not possible, since
h
+
1
<
p
. It follows that we can
group the elements of
S
in
p
−
3
2
distinct pairs
(
h
,
h
)
such that
hh
≡
1
(
mod
p
)
.
Multiplying these congruences gives
(
p
−
2
)
! ≡
1
(
mod
p
)
, and the conclusion
follows.
Do'stlaringiz bilan baham: |
