Number-Theory-Homework-5

Prévia do material em texto

PROBLEM SET 5
MATH 115
NUMBER THEORY
PROFESSOR PAUL VOJTA
NOAH RUDERMAN
Problems 3.2.7, 3.2.8, 3.2.18, 3.3.4, 3.3.15, 3.4.1a-f, 3.3.4, 3.3.10, 3.5.1, 3.5.3, 3.5.11, and
3.5.12 from An Introduction to The Theory of Numbers, 5th edition, by Ivan Niven, Herbert
S. Zuckerman, and Hugh L. Montgomery
Date: July 28, 2014.
1
Problem (3.2.7)
Solution.
We aim to find for which primes p the congruence x2 ≡ 13 mod p has a solution.
First we note that p = 2 and p = 13 are trivial solutions because both congruence classes
of 2 are quadratic residues and 02 ≡ 0 mod 13. Next we note that the congruence will have
a solution if the Legendre symbol
(
13
p
)
is equal to 1, by definition. By theorem 3.4 we see
that (
13
p
)( p
13
)
= (−1)
13−1
2
· p−1
2
= (−1)6·
p−1
2
=
(
(−1)6
) p−1
2
= (1)
p−1
2
= 1.
Clearly,
(
13
p
)
= 1 if and only if
(
p
13
)
= 1. By theorem 3.1(1), we see that( p
13
)
≡ p
13−1
2 mod 13
≡ p6 mod 13.
Therefore, 13 is a quadratic residue modulo p if and only if p6 ≡ 1 mod 13. With Mathemat-
ica (see figure 1), we see that p6 ≡ 1 mod 13 if p ≡ 1, 3, 4, 9, 12 mod 13. So the solutions
are p = 2, p = 13, or p ≡ 1, 3, 4, 9, 12 mod 13.
In[969]:= For @i = 0, i < 13, i ++,
Module @8f, x <,
If@Mod @i ^ 6, 13D � 1, Print@iDD;
D
D
1
3
4
9
10
12
Figure 1. Mathematica code prints the solutions to x6 ≡ 1 mod 13
2
Problem (3.2.8)
Solution.
We want to find all primes p such that
(
10
p
)
= 1.
From theorem 3.1(2) we have (
10
p
)
=
(
2
p
)(
5
p
)
.
From theorem 3.3, we know that if p is an odd prime, then
(
2
p
)
= (−1) p
2−1
8 . If p is odd,
then p ≡ ±1,±3 mod 8. if p ≡ ±1 mod 8, then p2−1
8
is even. If p ≡ ±3 mod 8, then p2−1
8
is odd. From this, we see that(
2
p
)
=

1 if p ≡ ±1 mod 8
0 if p ≡ 0 mod 2
−1 if p ≡ ±3 mod 8
From theorem 3.4, quadratic reciprocity, we know that
(
5
p
)
=
(
p
5
)
given 5 ≡ 1 mod 4.
By theorem 3.1(1), (p
5
)
≡ p
5−1
2 mod 5
≡ p2 mod 5.
By lemma 2.10, p2 ≡ 1 mod 5 only has solutions for p ≡ ±1 mod 5. Thus,
(p
5
)
=

1 if p ≡ ±1 mod 5
0 if p ≡ 0 mod 5
−1 if p ≡ ±2 mod 5
We see that
(
10
p
)
= 1 when p ≡ ±1 mod 5 and p ≡ ±1 mod 8 or p ≡ ±2 mod 5 and
p ≡ ±3 mod 8. By the Chinese remainder theorem, there will be 2 · 2 + 2 · 2 = 8 solutions.
To find the solutions, first we solve the set of congruences
p ≡ ±1 mod 5
p ≡ ±1 mod 8.
Clearly, if p ≡ 1 mod 5 and p ≡ 1 mod 8, then p ≡ 1 mod 40 is a solution. A similar
argument can be used to show p ≡ −1 mod 40 is a solution. To solve the set of congruences
p ≡ −1 mod 5
p ≡ 1 mod 8,
we start with the second congruence whose solution is 1 + 8k for k ∈ Z. Plugging this into
the first congruence, we see that
1 + 8k ≡ −1 mod 5
3
8k ≡ −2 mod 5
3k ≡ 3 mod 5
k ≡ 1 mod 5,
so k = 1 + 5l for l ∈ Z. Now we have our solution
1 + 8k = 1 + 8(1 + 5l)
= 9 + 40l.
For a solution p, we see that p ≡ 9 mod 40.
Now we solve the final congruence
p ≡ 1 mod 5
p ≡ −1 mod 8,
We start with the solution to the second congruence, −1 + 8k, k ∈ Z. Plugging this into the
first congruence, we see that
−1 + 8k ≡ 1 mod 5
8k ≡ 2 mod 5
3k ≡ −3 mod 5
k ≡ −1 mod 5,
so k = −1 + 5l for l ∈ Z. Now we have our solution
−1 + 8k = −1 + 8(−1 + 5l)
= −9 + 40l
= 31 + 40l′ l′ ∈ Z
For a solution p, we see that p ≡ 31 mod 40.
At this point, our first four solutions are p ≡ ±1,±9 mod 40. Finding the remaining four
involves solving the set of congruences
p ≡ ±2 mod 5
p ≡ ±3 mod 8.
Finding the solutions to these congrunces is equally tedious. Since finding the solutions to
the chinese remainder theorem is not the point of this exercise, I will list the remaining four
solutions: p ≡ ±3,±13 mod 40.
Therefore,
(
10
p
)
= 1 when p ≡ ±1,±3,±9,±13 mod 40.
4
Problem (3.2.18)
Solution.
For q = 1111111111111, where q is prime, we wish to find whether or not 1001 is a quadratic
residue mod q.
First we note that 111 · 1001 = 111111. Using this, we see that
q =
(
111 · 1001 · 107 + 111 · 1001
)
+ 1
= (111 · 107 + 111)1001 + 1.
Since 0 ≤ 1 < 1001, by the division algorithm, 1 is the remainder when q is divided by 1001.
Thus, q ≡ 1 mod 1001. Since 1001 = 7 · 11 · 13, by theorem 2.3(3),
q ≡ 1 mod 7(1)
q ≡ 1 mod 11(2)
q ≡ 1 mod 13.(3)
By theorem 3.1(2), we have(
1001
q
)
=
(
7
q
)(
11
q
)(
13
q
)
.
Using theorem 3.1(3) and 3.4, we see that(
7
q
)
= −
(q
7
)
since q ≡ 3 mod 4 and 7 ≡ 3 mod 4
= −
(
1
7
)
from equation 1
= −1.
Likewise, we see that(
11
q
)
= −
( q
11
)
since q ≡ 3 mod 4 and 11 ≡ 3 mod 4
= −
(
1
11
)
from equation 2
= −1,
and (
13
q
)
=
( q
13
)
since 13 ≡ 1 mod 4
=
(
1
13
)
from equation 3
= 1
5
Now we have enough information to determine whether 1001 is a quadratic residue modulo
q. We see that (
1001
q
)
=
(
7
q
)(
11
q
)(
13
q
)
.
= −1 · −1 · 1
= 1.
By definition, 1001 is a quadratic residue modulo q.
6
Problem (3.3.4)
Solution.
We want to determine whether the congruence x4 ≡ 25 mod 1013 has solutions given that
1013 is prime.
We see that x4 = (x2)
2
= 25 mod 1013, so it is sufficient to prove that x2 ≡ ±5 mod 1013
has solutions.
First we consider x2 ≡ 5 mod 1013. Using theorem 3.4, or quadratic reciprocity, and the
fact that 5 ≡ 1 mod 4, we see that(
5
1013
)
=
(
1013
5
)
=
(
3
5
)
= −1,
because by inspection (a
5
)
=
{
1 if a ≡ ±1 mod 5
−1 if a ≡ ±3 mod 5
By definition, x2 ≡ 5 mod 1013 has no solutions.
Second we consider x2 ≡ −5 mod 1013. Using theorem 3.1, we see that(
−5
1013
)
=
(
−1
1013
)(
5
1013
)
= (−1)
1013−1
2 · (−1) (from our earlier work)
= (−1)506 · (−1)
= 1 · −1
= −1.
By definition, x2 ≡ −5 mod 1013 has no solutions.
Since x2 ≡ ±5 mod 1013 has no solutions and ±5 mod 1013 are the only solutions to
the congruence y2 ≡ 25 mod 1013, we see that (x2)2 = x4 ≡ 25 mod 1013 can have no
solutions.
7
Problem (3.3.15)
Solution.
We aim to show that for any prime p ≥ 7, there is some number n ∈ N where 1 ≤ n ≤ 9 and
(4)
(
n
p
)
=
(
n+ 1
p
)
= 1.
We have three cases
1. p ≡ ±1 mod 8:
Clearly,
(
1
p
)
= 1. By theorem 3.3,
(
2
p
)
= (−1) p
2−1
8 . Clearly,
(
2
p
)
= 1 if p
2−1
8
is even.
Since p ≡ ±1 mod 8, we may write p as 1 + 8k for some k ∈ Z. Now we see that
p = ±1 + 8k
p2 = 1± 16k + 64k
p2 − 1 = ±16k + 64k
p2 − 1
8
= ±2k + 8k
p2 − 1
8
≡ 0 mod 2,
so
(
1
p
)
= 1 and
(
2
p
)
= 1. Therefore, equation 4 is true for n = 1.
2. p ≡ ±1 mod 5:
Clearly,
(
4
p
)
= 1. By theorem 3.4, or quadratic reciprocity,
(
5
p
)
=
(
p
5
)
. By inspection,
the only quadratic residues modulo 5 are the congruence classes ±1. By assumption,
p ≡ ±1 mod 5, so
(
5
p
)
= 1. Therefore, equation 4 is true for n = 4.
3. p ≡ ±2 mod 5 and p ≡ ±3 mod 8:
Clearly,
(
9
p
)
= 1. Our earlier work in problem 3.2.8 shows us that
(
10
p
)
= 1 when p ≡ ±2
mod 5 and p ≡ ±3 mod 8. This is true by assumption, so equation 4 is true for n = 9.
Since p ≥ 7, we see that p is odd. We have covered all cases because p must be congruent
to one of ±1,±3 mod 8 and congruent to one of ±1,±2 mod 5. Therefore, equation 4 is
true for some n ∈ Z where 1 ≤ n ≤ 9.
8
Problem (3.4.1)
Solution.
a. For the binary quadratic form
f(x, y) = x2 + y2,
we have
d = b2 − 4ac
= 02 − 4(1)(1)
= −4
< 0,
so given that a and c have the same sign and a > 0, by theorem 3.11, f(x, y) is
positive definite.
b. For the binary quadratic form
f(x, y) = −x2 − y2,
Since x2 +y2 is positive definite and f(x, y) = −(x2 +y2), clearly f(x, y) is negative
definite.
c. For the binary quadratic form
f(x, y) = x2 − 2y2,
we have
d = b2 − 4ac
= 02 − 4(1)(−2)
= 8
> 0,
so by theorem 3.11, f(x, y) is indefinite.
d. For the binary quadratic form
f(x, y) = 10x2 − 9xy + 8y2
we have
d = b2 − 4ac
= (−9)2 − 4(10)(8)
= 81− 320
= −239
< 0.
We see that a = 10, c = 8 have the same sign and that a > 0, so by theorem 3.11,
f(x, y) is positive definite.
9
e. For the binary quadratic form
f(x, y) = x2 − 3xy + y2
we have
d = b2 − 4ac
= (−3)2 − 4(1)(1)
= 9− 4
= 5
> 0,
so by theorem 3.11, f(x, y) is indefinite.
f. For the binaryquadratic form
f(x, y) = 17x2 − 26xy + 10y2
we have
d = b2 − 4ac
= (−26)2 − 4(17)(10)
= 576− 680
= −104
< 0.
We see that a = 17 and c = 10 have the same sign and that a > 0, so by theorem
3.11, f(x, y) is positive definite.
10
Problem (3.3.4)
Solution.
First we find a formula for positive integers xk and yk such that (3 + 2
√
2)k = xk +
√
2yk.
We see that
(3 + 2
√
2)k =
k∑
i=0
(
k
i
)
3k−i(2
√
2)i
=
k∑
i=0
i even
(
k
i
)
3k−i(2
√
2)i +
k∑
j=0
j odd
(
k
j
)
3k−j(2
√
2)j
=
k∑
i=0
i even
(
k
i
)
3k−i · 2i · 2i/2 +
k∑
j=0
j odd
(
k
j
)
3k−j · 2j · (
√
2)j−1 ·
√
2
=
k∑
i=0
i even
(
k
i
)
3k−i · 2
3i
2 +
√
2
k∑
j=0
j odd
(
k
j
)
3k−j · 2
3j−1
2 .
Thus, such a representation is possible for
xk =
k∑
i=0
i even
(
k
i
)
3k−i · 2
3i
2
yk =
k∑
j=0
j odd
(
k
j
)
3k−j · 2
3j−1
2 .
Next we show that (3− 2
√
2)k = xk − yk.
(3− 2
√
2)k =
k∑
i=0
(
k
i
)
3k−i(−2
√
2)i
=
k∑
i=0
i even
(
k
i
)
3k−i(−2
√
2)i +
k∑
j=0
j odd
(
k
j
)
3k−j(−2
√
2)j
=
k∑
i=0
i even
(
k
i
)
3k−i(2
√
2)i · (−1)i +
k∑
j=0
j odd
(
k
j
)
3k−j(2
√
2)j · (−1)j
=
k∑
i=0
i even
(
k
i
)
3k−i(2
√
2)i −
k∑
j=0
j odd
(
k
j
)
3k−j(2
√
2)j
11
=
k∑
i=0
i even
(
k
i
)
3k−i · 2i · 2i/2 −
k∑
j=0
j odd
(
k
j
)
3k−j · 2j · (
√
2)j−1 ·
√
2
=
k∑
i=0
i even
(
k
i
)
3k−i · 2
3i
2 −
√
2
k∑
j=0
j odd
(
k
j
)
3k−j · 2
3j−1
2
= xk −
√
2yk
Now we deduce that x2k − 2y2k = 1 for k = 1, 2, 3. . . ..
We see that
x2k − 2y2k = (xk +
√
2yk)(xk −
√
2yk)
= (3 + 2
√
2)k(3− 2
√
2)k
=
[
(3 + 2
√
2)(3− 2
√
2)
]k
= (9− 4 · 2)k
= (9− 8)k
= 1k
= 1 for all k = 1, 2, 3, . . .
Now we show gcd(xk, yk) = 1. By theorem 1.3, the greatest common divisor or x
2
k and y
2
k is
the smallest positive integer that is a linear combination of the two with integer coefficients.
Since we have showed that x2k − 2yk = 1, we see that gcd(x2k, y2k) = 1 because there are
no positive integers smaller than 1. By definition, two coprime numbers share no prime
factors. Since the prime factors of xk are a subset of x
2
k and the prime factors of yk are a
subset of y2k, we see that xk, yk cannot share any prime factors. Thus, they are coprime and
gcd(xk, yk) = 1 for all k ∈ N.
Next we show that xk+1 = 3xk + 4yk and yk+1 = 2xk + 3yk for all k ∈ N. We see that
xk =
k∑
i=0
i even
(
k
i
)
3k−i · 2
3i
2
xk+1 =
k+1∑
i=0
i even
(
k + 1
i
)
3k+1−i · 2
3i
2
yk =
k∑
j=0
j odd
(
k
j
)
3k−j · 2
3j−1
2
yk+1 =
k+1∑
j=0
j odd
(
k + 1
j
)
3k+1−j · 2
3j−1
2 .
12
We see that
3xk + 4yk = 3
k∑
i=0
i even
(
k
i
)
3k−i · 2
3i
2 + 4
k∑
j=0
j odd
(
k
j
)
3k−j · 2
3j−1
2
=
k∑
i=0
i even
(
k
i
)
3k+1−i · 2
3i
2 +
k∑
j=0
j odd
(
k
j
)
3k−j · 2
3j+3
2
=
k+1∑
i=0
i even
(
k
i
)
3k+1−i · 2
3i
2 +
k+1∑
j=0
j even
(
k
j − 1
)
3k−(j−1) · 2
3(j−1)+3
2
=
k+1∑
i=0
i even
(
k
i
)
3k+1−i · 2
3i
2 +
(
k
i− 1
)
3k−(i−1) · 2
3(i−1)+3
2
=
k+1∑
i=0
i even
[(
k
i
)
+
(
k
i− 1
)]
3k+1−i · 2
3i
2
=
k+1∑
i=0
i even
(
k + 1
i
)
3k+1−i · 2
3i
2
= xk+1,
where we have made use of the equality(
n
k
)
=
(
n
n− k
)
,
as outlined in equation 1.10 of Zuckerman et al.
Likewise, we see that
2xk + 3yk = 2
k∑
i=0
i even
(
k
i
)
3k−i · 2
3i
2 + 3
k∑
j=0
j odd
(
k
j
)
3k−j · 2
3j−1
2
=
k∑
i=0
i even
(
k
i
)
3k−i · 2
3i+2
2 +
k∑
j=0
j odd
(
k
j
)
3k+1−j · 2
3j−1
2
=
k+1∑
i=0
i odd
(
k
i− 1
)
3k−(i−1) · 2
3(i−1)+2
2 +
k∑
j=0
j odd
(
k
j
)
3k+1−j · 2
3j−1
2
=
k+1∑
j=0
j odd
[(
k
j
)
+
(
k
j − 1
)]
3k+1−j2
3j−1
2
13
=
k+1∑
j=0
j odd
(
k + 1
j
)
3k+1−j · 2
3j−1
2
= yk+1
Next we show that {xk} and {yk} are strictly increasing sequences.
For i, k ∈ N, we see that
−i < 2k + 2
−i+ (k + 1) < 2k + 1 + (k + 1)
k − i+ 1 < 3k + 3
(k)(k − 1)(k − 2) · · · (k − i+ 2)
(i)!
(k − i+ 1) < 3(k + 1)(k)(k − 1)(k − 2) · · · (k − i+ 2)
(i)!
(k)(k − 1)(k − 2) · · · (k − i+ 2)(k − i+ 1)
(i)!
< 3
(k + 1)(k)(k − 1)(k − 2) · · · (k − i+ 2)
(i)!(
k
i
)
< 3
(
k + 1
i
)
3k−i
(
k
i
)
< 3k−i · 3 ·
(
k + 1
i
)
(
k
i
)
· 3k−i <
(
k + 1
i
)
· 3k+1−i.
Suppose i is even. From this we see that(
k
i
)
· 3k−i <
(
k + 1
i
)
· 3k+1−i(
k
i
)
· 3k−i · 2
3i
2 <
(
k + 1
i
)
· 3k+1−i · 2
3i
2
xk < xk+1.
It is easy to see that for m < n, xm < xn. Thus, {xk} is a monotonic strictly increasing
sequence.
Suppose i is odd. From this we see that(
k
i
)
· 3k−i <
(
k + 1
i
)
· 3k+1−i(
k
i
)
· 3k−i · 2
3i+1
2 <
(
k + 1
i
)
· 3k+1−i · 2
3i+1
2
yk < yk+1.
It is easy to see that for m < n, ym < yn. Thus, {yk} is a monotonic strictly increasing
sequence.
Finally we show that 1 has infinitely many proper representations by the quadratic form
x2 − 2y2.
We have showed that x2k − 2y2k = 1 for k ∈ N. Furthermore, we showed gcd(xk, yk) = 1
for k ∈ N. Lastly, we showed that xm 6= xn for m 6= n because m < n implies xm < xn.
14
Likewise, we showed that ym 6= yn for m 6= n because m < n implies ym < yn. From this, we
can conclude that there is an infinite sequence {(xk, yk)} whose distinct members properly
represent 1.
15
Problem (3.3.10)
Solution.
We want to show that for f(x, y) = ax2 + bxy + cy2, a quadratic form with integral coeffi-
cients, that there exist integers x0, y0 not both 0 such that f(x0, y0) = 0, if and only if the
discriminant d of f(x, y) is a perfect square, possibly 0.
−→
Suppose there exist two integers, x0 and y0, not both 0, such that f(x0, y0) = 0. We know
that
4af(x0, y0) = (2ax0 + by0)
2 − dy20 = 0.
Call v = 2ax0 + by0. We see that
v2 = dy20
v2
y20
= d for y0 6= 0(
v
y0
)2
= d.
Thus, if y0 6= 0, then d is a perfect square. If y0 = 0, then f(x0, 0) = ax20 = 0, so a = 0.
Given that d = b2 − 4ac, if a = 0 then d = b2, so again d is a perfect square.
←−
Suppose d is a perfect square. Let d = e2 for some e ∈ Z. Given
4af(x0, y0) = (2ax0 + by0)
2 − dy0,
we see that
(2ax0 + by0)
2 − dy20 = (2ax0 + by0)2 − e2y20
= (2ax0 + by0 + ey0)(2ax0 + by0 − ey0)
= (2ax0 + (b+ e)y0)(2ax0 + (b− e)y0).
We see that x0 = (b − e), y0 = −2a and x0 = (b + e), y0 = −2a are two solutions. If x0
and y0 are not both 0, we are done, so we suppose that they are both 0. Then −2a = 0
implies a = 0 and b − e = 0 and b + e = 0 imply b = e = 0. Plugging in a = b = 0, we
see that f(x, y) = cy2. Clearly, x0 = 1, y0 = 0 is a solution to f(x, y) = 0, and they are
not both zero. Thus if d is a perfect square, there exist integers x0, y0 not both 0, such that
f(x0, y0) = 0. �
16
Problem (3.5.1)
Solution.
We want to find a reduced form equivalent to the form
f(x, y) = 7x2 + 25xy + 23y2.
We see that in the original form, a = 7, b = 25, and c = 23. We see that 25 = b 6≤ |a| = 7,
so we first apply the matrix [
1 −2
0 1
]
.
From equations 3.7a-c, we get the new form
A1x
2 +B1xy + C1y
2,
where
A1 = f(1, 0) = a
= 7
B1 = 2am12 + b
= 2 · 7 · −2 + 25
= −28 + 25
= −3
C1 = am
2
12 + bm12 + c
= 7 · (−2)2 + 25 · (−2) + 25
= 7 · 4− 50 + 23
= 28− 50 + 23
= 1
Now we have
f1(x, y) = 7x
2 − 3xy + y2,
where f ∼ f1.
We see that |A1| 6< |C1| so we apply the matrix[
0 1
1 0
]
.
From equations 3.7a-c, we get the new form
A2x
2 +B2xy + C2y
2,
where
A2 = C1
= 1
B2 = −B1
17
= −(−3)
= 3
C2 = A1
= 7
Now we have
f2(x, y) = x
2 + 3xy + 7y2,
where f2 ∼ f1.
Again, we see that B2 6≤ |A2|, so we apply the matrix[
1 −1
0 1
]
to get
A3 = f(1, 0) = a
= 1
B3 = 2am12 + b
= 2 · 1 · −1 + 3
= −2 + 3
= 1
C3 = am
2
12 + bm12 + c
= 1 · (−1)2 + 3 · (−1) + 7
= 1− 3 + 7
= 5
Now we have
f3(x, y) = x
2 + xy + 5y2,
where f3 ∼ f2, and f3 is in reduced form.
By transitivity, f3 ∼ f .
18
Problem (3.5.3)
Solution.
For x, y ∈ Z, we want to show that there exist u, v ∈ Z such that
[
x y
u v
]
∈ Γ if and only if
gcd(x, y) = 1.
By theorem 1.3, gcd(x, y) = 1 if and only if we can write
xv + yu′ = 1,
for some u′, v ∈ Z. Let u = −u′. We have
xv − yu = 1.
Consider the matrix
M =
[
x y
u v
]
.
We see that M ∈ Γ if and only if gcd(x, y) = 1 because mij ∈ Z and det M = xv − yu = 1
if and only if gcd(x, y) = 1. �19
Problem (3.5.11)
Solution.
Suppose that ax2 + bxy + cy2 ∼ Ax2 + Bxy + Cy2. We want to show that gcd(a, b, c) =
gcd(A,B,C).
Let f(x, y) = ax2 + bxy+ cy2 and h(x, y) = Ax2 +Bxy+Cy2. Since f ∼ h, they represent
the same points. Let g = gcd(a, b, c) and G = gcd(A,B,C). Clearly, f(x,y)
g
∈ Z. Because f
and h represent the same points, h(x,y)
g
∈ Z as well. We see that h(1, 0) = A and h(0, 1) = C,
so g | A and g | C. Again, h(1, 1) = A + B + C and because g | h(x, y), then g | B as well.
So g is a common divisor of A,B, and C. Thus, g | G.
Likewise, G | h(x, y) G | f(x, y) for all x, y ∈ Z. We see that f(1, 0) = a and f(0, 1) = c,
so G | a and G | c. Again, f(1, 1) = a+ b+ c and because G | f(x, y), then G | b as well. So
G is a common divisor of a,b, and c. Thus, G | g.
Since g | G and G | g, g = ±G. But the greatest common divisor is always positive, so
g = G.
20
Problem (3.5.12)
Solution.
Suppose f(x, y) = ax2 + bxy + cy2 is a positive semidefinite quadratic form of discriminant
0. Let g = gcd(a, b, c). We want to show that f is equivalent to the form gx2.
We see that d = b2 − 4ac = 0, so
(5) ac =
(
b
2
)2
,
So the product ac is a square. Consider the prime factorization of a and c such that
a =
∏
p
pα(p)
c =
∏
p
pγ(p),
for primes p. Clearly,
(6) α(p) + γ(p) ≡ 0 mod 2.
Let g = gcd(a, b, c) be factored as
g =
∏
p
pmin(α(p),β(p),γ(p)).
Considering equation 5, we see that min(α(p), β(p), γ(p)) = min
(
α(p), α(p)+γ(p)
2
, γ(p)
)
, if
p 6= 2 and min
(
α(2), α(2)+γ(2)+1
2
, γ(2)
)
, if p = 2. Furthermore, we see that if α(p) ≤ γ(p),
then
α(p) =
2α(p)
2
=
α(p) + α(p)
2
≤ γ(p) + α(p)
2
,
and if γ(p) ≤ α(p), then
γ(p) =
2γ(p)
2
=
γ(p) + γ(p)
2
≤ γ(p) + α(p)
2
.
Therefore, the exponents of the greatest common divisor in its prime factorization have the
form min(α(p), γ(p)).
21
By definition of a divisor, there is some n ∈ Z such that ng = a. Consider the prime
factorization of n. We see that
n = 2j
∏
p 6=2
pα(p)−min(α(p),γ(p)),
for some j ∈ N. From equation 6, we see that α(p) and γ(p) have the same parity. That is,
they are both even or both odd.
Thus, we see that α(p)−min(α(p), γ(p)) is even, so n is a perfect square. Let m2 = n for
some m ∈ Z. We see that
4af(x, y) = (2ax+ by)2 − dy2
4af(x, y) = (2ax+ by)2
f(x, y) =
(2ax+ by)2
4a
f(x, y) =
g2
(
2ax
g
+ by
g
)2
4ng
f(x, y) =
g
(
2ax
g
+ by
g
)2
4n
f(x, y) =
g
(
2ax
g
+ by
g
)2
4m2
f(x, y) = g
(
2ax+ by
2mg
)2
,
so all values of f(x, y) can be represented by gx2.
Call h(x, y) = gx2. We see that
f(x, y) = g
(
2a
2mg
x+
b
2mg
y, ux+ vy
)
,
where u and v are such that
a
mg
v − b
2mg
u = 1.
Such numbers u, v will exist if gcd
(
a
mg
, b
2mg
)
= 1. We also see that a
mg
= m because
a = ng = m2g.
We aim to show that gcd
(
m, b
2mg
)
= 1. We see that ac = m2gc =
(
b
2
)2
, so m2 | (b2/4), so
m | (b/2).
Now we note that if gcd(a, b, c) = g, then gcd
(
a
g
, b
g
, c
g
)
= 1. We see that
ac =
(
b
2
)2
c =
1
a
(
b
2
)2
22
c =
1
m2g
(
b
2
)2
c =
1
m2g
· b
2
· b
2
c
g
= · b
2mg
· b
2mg
.
Also,
a
g
=
m2g
g
= m2.
So
gcd
(
m2,
b
g
,
b
2mg
· b
2mg
)
= 1.
Clearly, gcd
(
m2,
(
b
2mg
)2)
= 1 so we can conclude that gcd
(
m, b
2mg
)
= 1 considering their
prime factorizations.
Therefore, there will be u, v which satisfy
a
mg
v − b
2mg
u = 1,
and the matrix [
m b
2mg
u v
]
∈ Γ
defines the transformation from h to f . By definition, h ∼ f .
23