|
Alternative proof.
The property is trivially true when
p
=
2, so assume that
p
is
odd. By Fermat’s little theorem, the polynomial
x
p
−
1
−
1 has for its
p
−
1 distinct
roots modulo
p
the numbers 1
,
2
, . . . ,
p
−
1. According to Theorem 7.1.1 we have
(
x
−
1
)(
x
−
2
)
· · ·
(
x
−
p
+
1
)
≡
x
p
−
1
−
1
(
mod
p
).
By setting
x
=
0 we obtain
(
−
1
)
p
−
1
(
p
−
1
)
! ≡ −
1
(
mod
p
).
Since
p
−
1 is even, the result follows.
Remark.
The converse is true, that is, if
n
|
(
n
−
1
)
! +
1 for an integer
n
≥
2,
then
n
is a prime. Indeed, if
n
were equal to
n
1
n
2
for some integers
n
1
,
n
2
≥
2,
we would have
n
1
|
1
·
2
· · ·
n
1
· · ·
(
n
−
1
)
+
1, which is not possible.
1
John Wilson (1741–1793), English mathematician who published this result without proof. It was
first proved in 1773 by Lagrange, who showed that the converse is also true.
142
I Fundamentals, 7. More on Divisibility
Problem 7.4.1.
If p is an odd prime, then the remainder when
(
p
−
1
)
!
is divided
by p
(
p
−
1
)
is p
−
1
.
Solution.
We need to show that
(
p
−
1
)
! ≡
p
−
1
(
mod
p
(
p
−
1
))
.
From Wilson’s theorem we obtain
(
p
−
1
)
! −
(
p
−
1
)
≡
0
(
mod
p
)
. Because
(
p
−
1
)
! −
(
p
−
1
)
≡
0
(
mod
p
−
1
)
and gcd
(
p
,
p
−
1
)
=
1, we get
(
p
−
1
)
! −
(
p
−
1
)
≡
0
(
mod
p
(
p
−
1
)).
Remark.
Generally, if
a
≡
b
(
mod
u
)
,
a
≡
b
(
mod
v)
, and gcd
(
u
, v)
=
1, then
a
≡
b
(
mod
u
v)
.
Problem 7.4.2.
Let p be an odd prime and a
1
,
a
2
, . . . ,
a
p
an arithmetic sequence
whose common difference is not divisible by p. Prove that there is an i
∈ {
1
,
2
,
. . .
, p
}
such that a
i
+
a
1
a
2
· · ·
a
p
≡
0
(
mod
p
2
)
.
Solution.
Note that
a
1
,
a
2
, . . . ,
a
p
give distinct remainders when divided by
p
.
Take
i
such that
a
i
≡
0
(
mod
p
)
. It follows that
a
1
a
2
· · ·
a
p
a
i
≡
(
p
−
1
)
!
(
mod
p
).
From Wilson’s theorem, we have
(
p
−
1
)
! ≡ −
1
(
mod
p
)
, and the conclusion
follows.
Problem 7.4.3.
Let a and n be positive integers such that n
≥
2
and
gcd
(
a
,
n
)
=
1
. Prove that
a
n
−
1
+
(
n
−
1
)
! ≡
0
(
mod
n
)
if and only if n is a prime.
Solution.
If
n
is a prime, the conclusion follows from Fermat’s little theorem and
Wilson’s theorem.
For the converse, assume by way of contradiction that
n
=
n
1
n
2
, where
n
1
≥
n
2
≥
2.
Because
n
|
a
n
−
1
+
(
n
−
1
)
!
, it follows that
n
1
|
a
n
−
1
+
(
n
−
1
)
!
, that is,
n
1
|
a
n
−
1
, contradicting the hypothesis gcd
(
a
,
n
)
=
1.
Problem 7.4.4.
(1) If p is a prime, then for any positive integer n
<
p,
(
n
−
1
)
!
(
p
−
n
)
! ≡
(
−
1
)
n
(
mod
p
).
(2) If p is a prime, then
p
−
1
k
≡
(
−
1
)
k
(
mod
p
)
for all k
=
0
,
1
, . . .
,
p
−
1
.
Solution.
(1) The property is obvious for
p
=
2, so assume that
p
is odd. From
Wilson’s theorem,
(
p
−
1
)
! ≡ −
1
(
mod
p
)
; hence
(
n
−
1
)
!
n
(
n
+
1
)
· · ·
(
p
−
1
)
≡ −
1
(
mod
p
).
7.4. Wilson’s Theorem
143
This is equivalent to
(
n
−
1
)
!
(
p
−
(
p
−
n
))(
p
−
(
p
−
n
−
1
))
· · ·
(
p
−
1
)
≡ −
1
(
mod
p
).
But
p
−
k
≡ −
k
(
mod
p
)
,
k
=
1
,
2
, . . . ,
p
−
n
; hence
(
n
−
1
)
!
(
−
1
)
p
−
n
(
p
−
n
)
! ≡ −
1
(
mod
p
),
and taking into account that
p
is odd, the conclusion follows.
(2) We have
p
−
1
k
=
(
p
−
1
)
!
k
!
(
p
−
k
−
1
)
!
,
hence
k
!
(
p
−
k
−
1
)
!
p
−
1
k
=
(
p
−
1
)
! ≡ −
1
(
mod
p
)
. Applying the result in
(1) for
n
=
k
+
1, it follows that
k
!
(
p
−
k
−
1
)
! ≡
(
−
1
)
k
+
1
(
mod
p
)
and we are
done.
Additional Problems
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
).
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)
Problem 7.4.7.
For each positive integer
n
, find the greatest common divisor of
n
! +
1 and
(
n
+
1
)
!
.
(1996 Irish Mathematical Olympiad)
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)
8
Diophantine Equations
8.1
Linear Diophantine Equations
An equation of the form
a
1
x
1
+ · · · +
a
n
x
n
=
b
,
(
1
)
where
a
1
,
a
2
, . . . ,
a
n
,
b
are fixed integers, is called a
linear Diophantine
1
equa-
tion
. We assume that
n
≥
1.
The main result concerning linear Diophantine equations is the following:
Theorem 8.1.1.
Equation (1) is solvable if and only if
gcd
(
a
1
, . . . ,
a
n
)
|
b
.
In case of solvability, one can choose n
−
1
solutions such that any solution is
a integer linear combination of those n
−
1
.
Proof.
Let
d
=
gcd
(
a
1
, . . . ,
a
n
)
. If
b
is not divisible by
d
, then (1) is not solvable,
since for any integers
x
1
, . . . ,
x
n
the left-hand side of (1) is divisible by
d
and the
right-hand side is not.
Actually, we need to prove that gcd
(
x
1
,
x
2
, . . . ,
x
n
)
is a linear combination
with integer coefficients of
x
1
,
x
2
, . . . ,
x
n
. For
n
=
2 this follows from Proposi-
tion 1.3.1. Since
gcd
(
x
1
, . . . ,
x
n
)
=
gcd
(
gcd
(
x
1
, . . . ,
x
n
−
1
),
x
n
),
we obtain that gcd
(
x
1
, . . . ,
x
n
)
is a linear combination of
x
n
and gcd
(
x
1
, . . .
,
x
n
−
1
)
; thus by the induction hypothesis, it is a linear combination of
x
1
, . . . ,
x
n
−
1
,
x
n
.
1
Diophantus of Alexandria (ca. 200–284), Greek mathematician sometimes known as “the father
of algebra” who is best known for his book
Arithmetica
. This book had an enormous influence on the
development of number theory.
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_8,
145
146
Do'stlaringiz bilan baham: |
