|
II Solutions, 7. More on Divisibility
n
|
m
3
n
−
1. Combining with
n
|
1
+
m
3
n
+
m
2
·
3
n
it follows that
n
=
3. If
k
≥
n
+
1,
then
d
=
3
n
+
1
and
d
|
ϕ(
n
)
implies
d
<
n
, impossible, since 3
n
+
1
>
n
. Therefore
n
=
3 and, consequently,
m
≡
1
(
mod 3
)
.
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.
Solution.
Set
d
=
o
n
(
a
)
. Since
n
|
a
n
−
1
−
1, it follows that
d
|
n
−
1. If
d
<
n
−
1,
then we contradict the hypothesis that
n
does not divide
a
d
−
1. Hence
d
≥
n
−
1
and consequently
d
=
n
−
1.
On the other hand, we have
d
|
ϕ(
n
)
; hence
n
−
1
|
ϕ(
n
)
. Taking into account
that
ϕ(
n
)
≤
n
−
1, we find that
ϕ(
n
)
=
n
−
1, and it follows that
n
must be 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)
Solution.
Without loss of generality assume
p
≤
q
; the unique solution will be
(
11
,
17
)
, for which one may check the congruence using the Chinese remainder
theorem. We first have 2
3
pq
≡
2
(
mod 3
)
, which means that
p
and
q
are odd. In
addition, if
α
is a primitive root mod
p
, then
α
3
pq
−
1
≡
1
(
mod
p
)
implies that
p
−
1 divides 3
pq
−
1 as well as 3
pq
−
1
−
3
q
(
p
−
1
)
=
3
q
−
1, and conversely
that
q
−
1 divides 3
p
−
1. If
p
=
q
, we now deduce
p
=
q
=
3, but 4
27
≡
1
(
mod 27
)
, so this fails. Hence
p
<
q
.
Since
p
and
q
are odd primes,
q
≥
p
+
2, so
(
3
p
−
1
)/(
q
−
1
) <
3. Since
this quantity is an integer, and it is clearly greater than 1, it must be 2. That is,
2
q
=
3
p
+
1. On the other hand,
p
−
1 divides 3
q
−
1
=
(
9
p
+
1
)/
2 as well as
(
9
p
+
1
)
−
(
9
p
−
9
)
=
10. Hence
p
=
11,
q
=
17.
Remark.
A composite integer
n
such that
a
n
≡
a
(
mod
n
)
for all integers
a
is
called a
Carmichael number
. Very recently, W.R. Alford, A. Granville, and C.
Pomerance [
Annals Math.
, 139(1994), 703–722] proved that there are infinitely
many Carmichael numbers. Using the ideas outlined in the solution of the above
problem, one can show that
n
is a Carmichael number if and only if it is of the
form
p
1
p
2
· · ·
p
k
, with
p
i
different prime numbers such that
p
i
−
1
|
n
−
1 for all
i
=
1
,
2
, . . . ,
k
and
k
>
1.
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
309
Solution.
Note that
p
p
−
1
p
−
1
=
p
p
−
1
+· · ·+
p
+
1 must have at least one prime factor
q
that is not congruent to 1
(
mod
p
2
)
. We will show that this
q
works. Note that
p
p
≡
1
(
mod
q
)
and that
q
p
−
1. For the latter, we note that if
q
|
p
−
1 then
p
p
−
1
+ · · · +
p
+
1
≡
p
≡
1
(
mod
q
)
, a contradiction. Hence
o
q
(
p
)
=
p
and
q
≡
1
(
mod
p
)
. Suppose now that
q
|
n
p
−
p
for some integer
n
. Then
n
p
≡
p
(
mod
q
)
and
n
p
2
≡
p
p
≡
1
(
mod
q
)
. Hence
o
q
(
n
)
=
p
2
and
q
≡
1
(
mod
p
2
)
,
contrary to our assumption.
Remark.
Taking
q
≡
1
(
mod
p
)
is natural, because for every other
q
,
n
p
takes
all possible residues modulo
p
(including
p
too). Indeed, if
p
q
−
1, then there is
an
r
∈
N
satisfying
pr
≡
1
(
mod
q
−
1
)
; hence for any
a
the congruence
n
p
≡
a
(
mod
q
)
has the solution
n
≡
a
r
(
mod
q
)
(see also the lemma from Problem
7.1.10).
7.4
Wilson’s Theorem
Problem 7.4.5.
Let p be an odd prime. Prove that
1
2
·
3
2
· · ·
(
p
−
2
)
2
≡
(
−
1
)
p
+
1
2
(
mod
p
)
and
2
2
·
4
2
· · ·
(
p
−
1
)
2
≡
(
−
1
)
p
+
1
2
(
mod
p
).
Solution.
Using Wilson’s theorem, we have
(
p
−
1
)
! ≡ −
1
(
mod
p
)
; hence
1
·
3
· · ·
(
p
−
2
)
2
·
4
· · ·
(
p
−
1
)
≡ −
1
(
mod
p
).
On the other hand,
1
≡ −
(
p
−
1
) (
mod
p
),
3
≡ −
(
p
−
3
) (
mod
p
), . . . ,
p
−
2
≡ −
p
−
(
p
−
2
)
(
mod
p
).
Therefore
1
·
3
· · ·
(
p
−
2
)
≡
(
−
1
)
p
−
1
2
(
2
·
4
· · ·
(
p
−
1
)) (
mod
p
),
and the conclusion follows.
Problem 7.4.6.
Show that there do not exist nonnegative integers k and m such
that k
! +
48
=
48
(
k
+
1
)
m
.
(1996 Austrian–Polish Mathematics Competition)
310
II Solutions, 7. More on Divisibility
Solution.
Suppose such
k
,
m
exist. We must have 48
|
k
!
, so
k
≥
6; one checks
that
k
=
6 does not yield a solution, so
k
≥
7. In that case
k
!
is divisible by 32
and by 9, so that
(
k
! +
48
)/
48 is relatively prime to 6, as then is
k
+
1.
If
k
+
1 is not prime, it has a prime divisor greater than 3, but this prime divides
k
!
and not
k
! +
48. Hence
k
+
1 is prime, and by Wilson’s theorem,
k
! +
1 is a
multiple of
k
+
1. Since
k
! +
48 is as well, we find that
k
+
1
=
47, and we need
only check that 46
!
/
48
+
1 is not a power of 47. We check that 46
!
/
48
+
1
≡
29
(
mod 53
)
(by canceling as many terms as possible in 46
!
before multiplying), but
that 47 has order 13 modulo 53 and that none of its powers is congruent to 29
modulo 53.
Remark.
Another argument for why
(
46
!
/
48
)
+
1 is not a power of 47 is the
following. One has that
(
46
!
/
48
)
+
1
≡
329
=
7
·
47
(
mod 47
2
)
. The least
computational argument I could find was that clearly
(
46
!
/
48
)
+
1 is congruent to
1 mod 5, 7, and 11 (as well as many other primes) and that
o
5
(
47
)
=
o
5
(
2
)
=
4,
o
7
(
47
)
=
o
7
(
5
)
=
6, and
o
11
(
47
)
=
o
11
(
3
)
=
5. Thus the least power of 47 that
is congruent to 1 mod all three of these primes is 47
lcm
(
4
,
6
,
5
)
=
47
60
. But clearly
(
46
!
/
48
)
+
1
<
47
46
<
47
60
. Thus
(
46
!
/
48
)
+
1 is not a power of 47.
Problem 7.4.7.
For each positive integer n, find the greatest common divisor of
n
! +
1
and
(
n
+
1
)
!
.
(1996 Irish Mathematical Olympiad)
Solution.
Let
f
(
n
)
=
gcd
(
n
!+
1
, (
n
+
1
)
!
)
. If
n
+
1 is composite, then each prime
divisor of
(
n
+
1
)
!
is a prime less than
n
, which also divides
n
!
and so does not
divide
n
! +
1. Hence
f
(
n
)
=
1. If
n
+
1 is prime, the same argument shows that
f
(
n
)
is a power of
n
+
1, and in fact
n
+
1
|
n
!+
1 by Wilson’s theorem. However,
(
n
+
1
)
2
does not divide
(
n
+
1
)
!
, and thus
f
(
n
)
=
n
+
1.
Problem 7.4.8.
Let p
≥
3
be a prime and let
σ
be a permutation of
{
1
,
2
, . . .
,
p
−
1
}
. Prove that there are i
=
j such that p
|
i
σ(
i
)
−
j
σ(
j
)
.
(1986 Romanian International Mathematical Olympiad Team Selection Test)
Solution.
Assume by contradiction that
p
does not divide
i
σ(
i
)
−
j
σ(
j
)
for any
i
,
j
=
1
,
2
, . . . ,
p
−
1,
i
=
j
. Then, the integers
i
σ(
i
)
,
i
=
1
,
2
, . . . ,
p
−
1, are
all not divisible by
p
and give distinct residues modulo
p
. We have
p
−
1
i
=
1
(
i
σ (
i
))
≡
p
−
1
i
=
1
i
=
(
p
−
1
)
! ≡ −
1
(
mod
p
).
On the other hand,
p
−
1
i
=
1
(
i
σ (
i
))
=
p
−
1
i
=
1
((
p
−
1
)
!
)
2
≡
1
(
mod
p
)
, a con-
tradiction.
Do'stlaringiz bilan baham: |
