A. Student

Math 124 Problem Set 6

1. -389 is negative, and thus not the sum of two squares. Since 3||12345, it is not the sum of two squares. Since 7||91210, it is not the sum of two squares. 729 = 27^{2} is a perfect square. Since 7||1729, it is not the sum of two squares. Finally, 151||68252 and 151 ≡ 3(mod 4), so it is not the sum of two squares. 2i. On input n, the program breaks up n into two parts and looks for a sum of two squares representation.

{squares(n) = local(y); for(x=1,floor(sqrt(n)), y=sqrt(n-x^{2}); if(y-floor(y)==0, return([x,floor(y)])) ); return(0) }

f(n) = for(x=1,n, a=squares(x); b=squares(n-x); if(a!=0 && b!=0, return([a,b])));} 2ii. 2001 = 1^{2} + 8^{2} + 44^{2}.

3. 625 There are two Pythagorean triples with 25 as the hypotenuse: (7, 24, 25) and (15, 20, 25). This gives two representations of 625 as the sum of two squares. Of course, 25^{2} is a third.

4. The forward direction is trivial. For the opposite direction, suppose that n is the sum of two rational squares: n = (\frac{a}{b})^{2} + (\frac{c}{d})^{2}, but it is not the sum of two integer squares. Then p^{r}||n, where p ≡ 3(mod 4) is a prime factor and r is odd. Now, nb^{2}d^{2} = (ad)^{2} + (bc)^{2}, so nb^{2}d^{2} is the sum of two integer squares. However, all the prime factors of b^{2}d^{2} have even exponent, so p^{s}||nb^{2}d^{2}, where s is still odd. This is a contradiction; therefore n must be the sum of two integer squares.

5. Suppose p = x^{2} + 2y^{2}, where p is an odd prime and x, y are integers. Then x^{2} + 2y^{2} ≡ 0(mod p), so (\frac{x}{y})^{2} ≡ −2(mod p) (since Z_{p} is a field). From Lecture 13, (\frac{2}{p}) = 1 iff p ≡ ±1(mod 8). Also, (\frac{−1}{p}) = 1 iff p ≡ 1(mod 4) ⇒ p ≡ 1, −3(mod 8). Since (\frac{−2}{p}) = (\frac{−1}{p}) · (\frac{2}{p}), we have (\frac{−2}{p}) = 1 iff p ≡ 1, 3(mod 8). Conversely, suppose p ≡ 1, 3(mod 8) is prime. Let r be such that r^{2} ≡ −2(mod p). Taking n = ⌊\sqrt{p}⌋ and applying Lemma 1.3 from Lecture 21, there exist integers a, b with 0 < b < \sqrt{p} such that

|−\frac{r}{p} − \frac{a}{b}| ≤ \frac{1}{b(n + 1)} < \frac{1}{b\sqrt{p}}.

Let c = rb + pa; then |c| < \frac{pb}{b\sqrt{p}} = \sqrt{p}, so 2b^{2} + c^{2} < 3p. Since c ≡ rb(mod p), we also have that 2b^{2} + c^{2} ≡ b^{2}(2 + r^{2}) ≡ 0(mod p). Therefore 2b^{2} + c^{2} = p or 2p. If 2b^{2} + c^{2} = p we are done. If 2b^{2} + c^{2} = 2p then c must be even (else 2b^{2} + c^{2} is odd). Put c = 2d; then

2p = 2b^{2} + c^{2} = 2b^{2} + 4d^{2} ⇒ p = b^{2} + 2d^{2},

as desired.

6. Let T_{m} be the mth triangular number. It is easy to see by induction that T_{m} = \frac{m(m+1)}{2}. Then

8T_{m}^{2} = 2m^{2}(m + 1)^{2} = (2T_{m})^{2} + (2T_{m})^{2},
8T_{m}^{2} + 1 = 2m^{2}(m + 1)^{2} + 1 = [(m − 1)(m + 1)]^{2} + [m(m + 2)]^{2},

8T_{m}^{2} + 2 = 2m^{2}(m + 1)^{2} + 2 = [m(m + 1) − 1]^{2} + [m(m + 1) + 1]^{2}.

This shows that 8T_{m}, 8T_{m} + 1 and 8T_{m} + 1 can be written as the sum of two squares.

7. Of any four consecutive integers, there is one n such that n ≡ −1(mod 4). Since all odd prime factors are congruent to ±1(mod 4), n must have some prime factor p ≡ −1(mod 4) with odd exponent. This implies that n is not representable as the sum of two squares.

8. We first solve

13x^{2} + 36xy + 25y^{2} = (ax + by)^{2} + (cx + dy)^{2} = (a^{2} + c^{2})x^{2} + 2(ab + cd)xy + (b^{2} + d^{2})y^{2},

and then check that ad − bc = 1. By inspection, we try a = 3, c = 2. Then b^{2} + d^{2} = 25 and 2b + 3d = 18, which again by inspection is satisfied by b = 4, d = 3. Since ad−bc = 1, the form is equivalent to x^{2} +y^{2}. As above, we solve

58x^{2} + 82xy + 29y^{2} = (ax + by)^{2} + (cx + dy)^{2} = (a^{2} + c^{2})x^{2} + 2(ab + cd)xy + (b^{2} + d^{2})y^{2},

and then check that ad − bc = 1. By inspection, we try a = 3, c = 7. Then b^{2} + d^{2} = 29 and 7b + 3d = 41, which again by inspection is satisfied by b = 2, d = 5. Since ad−bc = 1, the form is equivalent to x^{2} +y^{2}. We know that x = 17, y = 10 satisfies x^{2} + y^{2} = 389. To find x, y such that 13x^{2} + 36xy + 25y^{2}, We use the transformation above and solve for

17 = 3x + 4y, 10 = 2x + 3y.

The solution to this system is x= 11, y= -4. Indeed, 13 · 11^{2} − 36 · 11 · 4 + 25 · 4^{2} = 389.

9. The discriminants are equal: −24 = 162^{2} − 4 · 199 · 33 = 96^{2} − 4 · 35 · 66. However, the forms are not equivalent. To see this, we first show that 35x^{2} = 96xy + 66y^{2} is equivalent to 2x^{2} + 3y^{2}. As above, this means solving

35x^{2} = 96xy + 66y^{2} = 2(ax + by)^{2} + 3(cx + dy)^{2} = (2a^{2} + 3c^{2})x^{2} + 2(2ab + 3cd)xy + (2b^{2} + 3d^{2})y^{2}

over the integers such that ad − bc = 1. By inspection we see that a = 2, b = −3, c = 3, d = −4 is a solution, so the forms are equivalent. Now we show the first form is not equivalent to 2x^{2} + 3y^{2}. If we try to solve for as above, we encounter the equation 33 = 2b^{2} + 3d^{2}, which has no solutions over the integers (we can just check 0 ≤ b ≤ 5).