|
I Fundamentals, 9. Some Special Problems in Number Theory
If
p
=
4
u
+
1, then
n
=
2
u
−
u
=
u
and
p
2
−
1
8
=
2
u
2
+
u
. We have
n
≡
p
2
−
1
8
(
mod 2
)
and we are done.
If
p
=
4
v
+
3, then
n
=
2
v
+
1
−
v
=
v
+
1 and
p
2
−
1
8
=
2
v
2
+
3
v
+
1, and
again
n
≡
p
2
−
1
8
(
mod 2
)
.
The central result concerning the Legendre symbol is the so-called
quadratic
reciprocity law
of Gauss:
Theorem 9.1.3.
If p and q are distinct odd primes, then
q
p
p
q
=
(
−
1
)
p
−
1
2
·
q
−
1
2
.
Proof.
In Gauss’s lemma we take
a
=
q
and we get
q
p
=
(
−
1
)
n
. Let
"
m
i
=
1
b
i
=
b
and
"
n
j
=
1
c
j
=
c
. Then using the equality
{
b
1
, . . . ,
b
m
,
p
−
c
1
, . . . ,
p
−
c
n
} =
1
,
2
, . . . ,
p
−
1
2
,
it follows that
b
+
np
−
c
=
p
−
1
2
k
=
1
k
=
p
2
−
1
8
.
But from Gauss’s lemma we have
q
k
=
kq
p
,
k
=
1
,
2
, . . . ,
p
−
1; hence
q
p
2
−
1
8
=
p
p
−
1
2
k
=
1
%
kq
p
&
+
b
+
c
.
Summing up the last two relations gives
2
c
+
p
p
−
1
2
k
=
1
%
kq
p
&
+
p
2
−
1
8
(
1
−
q
)
−
np
=
0
.
Because 2
c
and 1
−
q
are even, it follows that
n
≡
p
−
1
2
k
=
1
%
kq
p
&
(
mod 2
),
and applying Gauss’s lemma again we obtain
q
p
=
(
−
1
)
"
p
−
1
2
k
=
1
#
kq
p
$
.
9.1. Quadratic Residues; the Legendre Symbol
171
Similarly, we derive the relation
p
q
=
(
−
1
)
"
p
−
1
2
j
=
1
#
j p
q
$
.
Multiplying the last two equalities and taking into account Landau’s identity
in Problem 3.2.5(b) of Chapter 3, the conclusion follows.
Problem 9.1.1.
Let k
=
2
2
n
+
1
for some positive integer n. Show that k is a prime
if and only if k is a factor of
3
(
k
−
1
)/
2
+
1
.
(1997 Taiwanese Mathematical Olympiad)
Solution.
Suppose
k
is a factor of 3
(
k
−
1
)/
2
+
1. This is equivalent to 3
(
k
−
1
)/
2
≡
−
1
(
mod
k
)
. Hence 3
k
−
1
≡
1
(
mod
k
)
. Let
d
be the order of 3 mod
k
. Then
d
(
k
−
1
)/
2
=
2
2
n
−
1, but
d
|
(
k
−
1
)
=
2
2
n
. Hence
d
=
2
2
n
=
k
−
1. Therefore
k
is prime.
Conversely, suppose
k
is prime. By the quadratic reciprocity law,
3
k
=
k
3
=
2
3
= −
1
.
By Euler’s criterion, 3
(
k
−
1
)/
2
≡
3
k
≡ −
1
(
mod
k
)
, as claimed.
Problem 9.1.2.
Prove that if n is a positive integer such that the equation x
3
−
3
x y
2
+
y
3
=
n has an integer solution
(
x
,
y
)
, then it has at least three such
solutions.
Show there are no solutions if n
=
2891
.
(23rd International Mathematical Olympiad)
Solution.
The idea of the solution is to find a nonsingular change of coordinates
with integer coefficients
(
x
,
y
)
→
(
ax
+
by
,
cx
+
d y
)
such that the polynomial
x
3
−
3
x y
2
+
y
3
does not change after changing coordi-
nates. Such a transformation can be found after noticing the identity
x
3
−
3
x y
2
+
y
3
=
(
y
−
x
)
3
−
3
x
2
y
+
2
x
3
=
(
y
−
x
)
3
−
3
(
y
−
x
)
x
2
+
(
−
x
)
3
.
Thus, such a transformation is
T
(
x
,
y
)
=
(
y
−
x
,
−
x
)
. It can be represented
by the linear transformation
T
x
y
=
−
1 1
−
1 0
x
y
=
−
x
+
y
−
x
.
172
I Fundamentals, 9. Some Special Problems in Number Theory
We have
T
2
=
−
1 1
−
1 0
−
1 1
−
1 0
=
0
−
1
1
−
1
and
T
3
=
0
−
1
1
−
1
−
1 1
−
1 0
=
1 0
0 1
.
Thus,
T
2
(
x
,
y
)
=
(
−
y
,
x
−
y
)
. Moreover, it is easy to see that if
x
3
−
3
x y
2
+
y
3
=
n
,
n
≥
0, then the pairs
(
x
,
y
)
,
(
−
y
,
x
−
y
)
, and
(
y
−
x
,
−
x
)
are distinct.
For the second part, observe that 2891
=
7
2
·
59. Suppose that
x
,
y
are integers
such that
x
3
−
3
x y
2
+
y
3
=
2891. Then
x
,
y
are relatively prime, because from
d
=
gcd
(
x
,
y
)
we obtain
d
3
|
2891. The numbers
x
,
y
are not divisible by 7; thus
they are invertible modulo 7. Thus, from the equation we obtain
y
x
3
−
3
y
x
2
+
1
≡
0
(
mod 7
).
This proves that the congruence
a
3
−
3
a
2
+
1
≡
0
(
mod 7
)
has a solution,
a
∈
Z
. Since 7 is not a divisor of
a
, by Fermat’s little theorem one
has
a
6
≡
1
(
mod 7
)
. There are two possibilities:
a
3
≡
1
(
mod 7
)
or
a
3
≡ −
1
(
mod 7
)
. When
a
3
≡
1
(
mod 7
)
we obtain
a
3
−
3
a
2
+
1
≡
0
(
mod 7
)
⇒
3
a
2
≡
2
(
mod 7
)
⇒
a
2
≡
3
(
mod 7
).
Using the Legendre symbol and the quadratic reciprocity law,
3
7
=
(
−
1
)
3
−
1
2
·
7
−
1
2
7
3
=
(
−
1
)
1
3
= −
1
.
This proves that 3 is not a square modulo 7. When
a
3
≡ −
1
(
mod 7
)
we
obtain the contradiction from 3
a
2
≡
0
(
mod 7
)
. Thus, the equation
x
3
−
3
x y
2
+
y
3
=
2891 has no solution in integers
(
x
,
y
)
.
Problem 9.1.3.
Let m
,
n be positive integers such that
A
=
(
m
+
3
)
n
+
1
3
m
is an integer. Prove that A is odd.
(1998 Bulgarian Mathematical Olympiad)
Solution.
If
m
is odd, then
(
m
+
3
)
n
+
1 is odd and
A
is odd. Now we suppose
that
m
is even. Since
A
is an integer,
0
≡
(
m
+
3
)
n
+
1
≡
m
n
+
1
(
mod 3
),
9.1. Quadratic Residues; the Legendre Symbol
173
so
n
=
2
k
+
1 is odd and
m
≡ −
1
(
mod 3
)
. We consider the following cases:
(a)
m
=
8
m
for some positive integer
m
. Then
(
m
+
3
)
n
+
1
≡
3
2
k
+
1
+
1
≡
4
(
mod 8
)
and 3
m
≡
0
(
mod 8
)
. So
A
is not an integer.
(b)
m
=
2
m
for some odd positive integer
m
, i.e.,
m
≡
2
(
mod 4
)
. Then
(
m
+
3
)
n
+
1
≡
(
2
+
3
)
n
+
1
≡
2
(
mod 4
)
and 3
m
≡
2
(
mod 4
)
. So
A
is odd.
(c)
m
=
4
m
for some odd positive integer
m
. Because
m
≡ −
1
(
mod 3
)
,
there exists an odd prime
p
such that
p
≡ −
1
(
mod 3
)
and
p
|
m
. Since
A
is an
integer,
0
≡
(
m
+
3
)
n
+
1
≡
3
2
k
+
1
+
1
(
mod
m
)
and 3
2
k
+
1
≡ −
1
(
mod
p
)
. Let
a
be a primitive root modulo
p
; let
b
be a positive
integer such that 3
≡
a
b
(
mod
p
)
. Thus
a
(
2
k
+
1
)
b
≡ −
1
(
mod
p
)
. Note that
(
p
/
3
)
=
(
−
1
/
3
)
= −
1. We consider the following cases.
(i)
p
≡
1
(
mod 4
)
. From the quadratic reciprocity law,
(
−
1
/
p
)
=
1, so
a
2
c
≡ −
1
≡
a
(
2
k
+
1
)
b
(
mod
p
)
for some positive integer
c
. Therefore
b
is even and
(
3
/
p
)
=
1. Again, from the
quadratic reciprocity law,
−
1
=
(
3
/
p
)(
p
/
3
)
=
(
−
1
)
(
3
−
1
)(
p
−
1
)/
4
=
1
,
a contradiction.
(ii)
p
≡
3
(
mod 4
)
. From the quadratic reciprocity law,
(
−
1
/
p
)
= −
1, so
a
2
c
+
1
≡ −
1
≡
a
(
2
k
+
1
)
b
(
mod
p
)
for some positive integer
c
. Therefore
b
is odd and
(
3
/
p
)
= −
1. Again, from the
quadratic reciprocity law,
1
=
(
3
/
p
)(
p
/
3
)
=
(
−
1
)
(
3
−
1
)(
p
−
1
)/
4
= −
1
,
a contradiction.
Thus for
m
=
4
m
and
m
odd,
A
is not an integer.
From the above, we see that if
A
is an integer,
A
is odd.
Problem 9.1.4.
Prove that
2
n
+
1
has no prime factors of the form
8
k
+
7
.
(2004 Vietnamese International Mathematical Olympiad Team Selection Test)
174
Do'stlaringiz bilan baham: |
