|
8.3. Nonstandard Diophantine Equations
165
Additional Problems
Problem 8.3.19.
Determine all triples
(
x
,
k
,
n
)
of positive integers such that
3
k
−
1
=
x
n
.
(1999 Italian Mathematical Olympiad)
Problem 8.3.20.
Find all pairs of nonnegative integers
x
and
y
that satisfy the
equation
p
x
−
y
p
=
1
,
where
p
is a given odd prime.
(1995 Czech–Slovak Match)
Problem 8.3.21.
Let
x
,
y
,
z
be integers with
z
>
1. Show that
(
x
+
1
)
2
+
(
x
+
2
)
2
+ · · · +
(
x
+
99
)
2
=
y
z
.
(1998 Hungarian Mathematical Olympiad)
Problem 8.3.22.
Determine all solutions
(
x
,
y
,
z
)
of positive integers such that
(
x
+
1
)
y
+
1
+
1
=
(
x
+
2
)
z
+
1
.
(1999 Taiwanese Mathematical Olympiad)
9
Some Special Problems in
Number Theory
9.1
Quadratic Residues; the Legendre Symbol
Let
a
and
m
be positive integers such that
m
=
0 and gcd
(
a
,
m
)
=
1. We say that
a
is a
quadratic residue
mod
m
if the congruence
x
2
≡
a
(
mod
m
)
has a solution.
Otherwise, we say that
a
is a quadratic nonresidue.
Let
p
be a prime and let
a
be a positive integer not divisible by
p
. The
Legen-
dre symbol
of
a
with respect to
p
is defined by
a
p
=
1 if
a
is a quadratic residue
(
mod
p
),
−
1 otherwise.
It is clear that the perfect squares are quadratic residues mod
p
. It is natural to
ask how many integers among 1
,
2
, . . . ,
p
−
1 are quadratic residues. The answer
is given in the following theorem.
Theorem 9.1.1.
Let p be an odd prime. There are
p
−
1
2
quadratic residues in the
set
{
1
,
2
, . . . ,
p
−
1
}
.
Proof.
Consider the numbers
k
2
,
k
=
1
,
2
, . . . ,
p
−
1
2
. These are quadratic residues,
and moreover, they are distinct. Indeed, if
i
2
≡
j
2
(
mod
p
)
, then it follows that
p
|
(
i
−
j
)(
i
+
j
)
, and since
i
+
j
<
p
, this implies
p
|
i
−
j
; hence
i
=
j
.
Conversely, if gcd
(
a
,
p
)
=
1 and the congruence
x
2
≡
a
(
mod
p
)
has a
solution
x
, then
x
=
q p
+
i
, where
−
p
−
1
2
≤
i
≤
p
−
1
2
and so
i
2
≡
q
(
mod
p
)
.
The basic properties of the Legendre symbol are as follows:
(1) (Euler’s criterion) If
p
is an odd prime and
a
an integer not divisible by
p
,
then
a
p
−
1
2
≡
a
p
(
mod
p
).
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_9,
167
168
I Fundamentals, 9. Some Special Problems in Number Theory
(2) If
a
≡
b
(
mod
p
)
, then
a
p
=
b
p
.
(3) (multiplicity)
a
1
···
a
n
p
=
a
1
p
· · ·
a
n
p
.
(4)
−
1
p
=
(
−
1
)
p
−
1
2
.
For Euler’s criterion, suppose that
a
p
=
1. Then
i
2
≡
a
(
mod
p
)
for some
integer
i
. We have gcd
(
i
,
p
)
=
1, and from Fermat’s little theorem,
i
p
−
1
≡
1
(
mod
p
)
. Hence
a
p
−
1
2
≡
1
(
mod
p
)
and we are done.
If
a
p
= −
1, then each of the congruences
x
p
−
1
2
−
1
≡
0
(
mod
p
)
and
x
p
−
1
2
+
1
≡
0
(
mod
p
)
has
p
−
1
2
distinct solutions in the set
{
1
,
2
, . . . ,
p
−
1
}
. The
p
−
1
2
quadratic residues
correspond to the first congruence, and the
p
−
1
2
quadratic nonresidues correspond
to the second. Hence if
a
is a quadratic nonresidue, we have
a
p
−
1
2
≡ −
1
(
mod
p
)
,
and we are done.
Remark.
From Fermat’s little theorem,
a
p
−
1
≡
1
(
mod
p
)
, and hence
p
|
(
a
p
−
1
2
−
1
)(
a
p
−
1
2
+
1
)
. From Euler’s criterion,
p
|
a
p
−
1
2
−
1 if and only if
a
is a quadratic residue mod
p
.
Property (2) is clear. For (3) we apply Euler’s criterion:
a
i
p
≡
a
p
−
1
2
i
(
mod
p
),
i
=
1
, . . . ,
n
.
Therefore
a
1
p
· · ·
a
n
p
≡
a
p
−
1
2
1
· · ·
a
p
−
1
2
n
=
(
a
1
· · ·
a
n
)
p
−
1
2
≡
a
1
· · ·
a
n
p
(
mod
p
).
In order to prove (4), note that
(
−
1
)
p
−
1
2
,
−
1
p
∈ {−
1
,
1
}
. Hence
p
|
(
−
1
)
p
−
1
2
−
−
1
p
is just Euler’s criterion for
a
= −
1.
The following theorem gives necessary and sufficient conditions under which
2 is a quadratic residue.
Theorem 9.1.2.
For any odd prime p,
2
p
=
(
−
1
)
p
2
−
1
8
.
Proof.
We need the following lemma.
9.1. Quadratic Residues; the Legendre Symbol
169
Lemma.
(Gauss
1
)
If a is a positive integer that is not divisible by p, then from the
division algorithm,
ka
=
pq
k
+
r
k
,
k
=
1
, . . . ,
p
−
1
2
.
Let b
1
, . . . ,
b
m
be the distinct remainders r
1
, . . . ,
r
(
p
−
1
)/
2
that are less than
p
2
and let c
1
, . . . ,
c
n
be the other distinct remaining remainders. Then
a
p
=
(
−
1
)
n
.
Proof of lemma.
We have
m
i
=
1
b
i
n
j
=
1
c
j
=
p
−
1
2
k
=
1
r
k
=
p
−
1
2
k
=
1
(
ka
−
pq
k
)
≡
p
−
1
2
k
=
1
ka
=
a
p
−
1
2
p
−
1
2
!
(
mod
p
).
Because
p
2
<
c
j
≤
p
−
1,
j
=
1
, . . . ,
n
, we have 1
≤
p
−
c
j
≤
(
p
−
1
)/
2. It
is not possible to have
p
−
c
j
=
b
i
for some
i
and
j
. Indeed, if
b
i
+
c
j
=
p
, then
p
=
as
−
pq
s
+
at
−
pq
t
, so
p
|
s
+
t
, which is impossible, since 1
≤
s
,
t
≤
(
p
−
1
)/
2.
Therefore the integers
b
1
, . . . ,
b
m
,
p
−
c
1
, . . . ,
p
−
c
n
are distinct and
{
b
1
, . . . ,
b
m
,
p
−
c
1
, . . . ,
p
−
c
n
} =
1
,
2
, . . . ,
p
−
1
2
.
We obtain
m
i
=
1
b
i
n
j
=
1
(
p
−
c
j
)
=
p
−
1
2
!
.
Finally,
(
−
1
)
n
m
i
=
1
b
i
n
j
=
1
c
j
≡
p
−
1
2
!
(
mod
p
)
;
hence
a
(
p
−
1
)/
2
≡
(
−
1
)
n
(
mod
p
)
. The conclusion now follows from Euler’s
criterion.
In order to prove the theorem we use Gauss’s lemma for
a
=
2. We have
{
r
1
,
r
2
, . . . ,
r
(
p
−
1
)/
2
} = {
2
,
4
, . . . ,
p
−
1
}
. The number of integers
k
such that
p
/
2
<
2
k
<
p
is
n
=
p
2
−
p
4
.
1
Karl Friedrich Gauss (1777–1855), German mathematician who is sometimes called the “prince
of mathematics”. Gauss proved in 1801 the fundamental theorem of arithmetic, and he published
one of the most brilliant achievements in mathematics,
Disquisitiones Arithmeticae
. In this book he
systematized the study of number theory and developed the algebra of congruences.
170
Do'stlaringiz bilan baham: |
