Math 124, HW #6, Page 1, December 12, 2001  Student, F.

1. (a) −389 is negative, so no.

(b) 12345 = 3 · 5 · 823 no, on account of 3 and 823.

(c) 91210 = 2 · 5 · 7 · 1303 no, on account of 7 and 1303.

(d) 729 = 3^{6} = 27^{2} + 0^{2} .

(e) 1729 = 7 · 13 · 19, no on account of 7 and 19.

(f) 68252 = 2^{2} · 113 · 151, no on account of 151.

2. (a) Hardly efficient, but this works:

    {sumoffoursquares(n) =
      local(x,y,z,w);
      for(x=0, floor(sqrt(n)),
        for(y=0,floor(sqrt(n-x^2)),
          for(z=0,floor(sqrt(n-x^2-y^2)),
            for(w=0,floor(sqrt(n-x^2-y^2-z^2)),
              if(n==x^2 + y^2 + z^2 + w^2, return([x,y,z,w]))
            )
          )
        )
      );
      error(n, " is not a sum of four squares");
    }

(b) 2001 = 1^{2} + 1^{2} + 14^{2} + 99^{2}

3. 325 = 1^{2} + 18^{2} = 6^{2} + 17^{2} = 10^{2} + 15^{2}. I found this with a for loop and a PARI program:

? ?sumoftwosquaresthrice
sumoftwosquaresthrice(n) = local(y); for(x=0,floor(sqrt(n)),
y=sqrt(n-x^2);if(y-floor(y)==0,return(thricehelpone(n,x,
floor(y)))));return();
? ?thricehelpone
thricehelpone(n, x, y) = local(xx, z); xx=x;for(x=x+1,
floor(sqrt(n)),z=sqrt(n-x^2);if(z-floor(z)==0,
return(thricehelptwo(n,xx,y,x,floor(z)))));return();
? ?thricehelptwo
thricehelptwo(n, xx, y, xxx, z) = local(w); for(x=xxx+1,
floor(sqrt(n)),w=sqrt(n-x^2);if(w-floor(w)==0,if((floor(w)!=xxx)
&(floor(w)!=xx),return([xx,y,xxx,z,x,floor(w)]))));return([xx,y,xxx,z])
? for(X=324,326,print(sumoftwosquaresthrice(X)))
[0, 18, 18, 0]
[1, 18, 6, 17, 10, 15]

4. Claim: A natural number n is a sum of two integers squares if and only if it is the sum of two rational squares. Proof: The forward direction is trivial, since integers are rational. (If n = x^{2} + y^{2} such that x, y ∈ ℤ, n = x^{2} + y^{2} such that x, y ∈ ℚ.)

Suppose n = (\frac{a}{b})^{2} +(\frac{c}{d})^{2}. Then, b^{2}d^{2}n = (ad)^{2} +(bc)^{2}. So b^{2}d^{2}n is a sum of two integer squares. Now, suppose n cannot be expressed as a sum of two integer squares. Then, by the theorem we showed in class, n has a prime factor of the form 4m+3 with an odd exponent. Let’s call this prime factor p, and call its power in the prime decomposition of n, g. Let p^{e} and p^{f} denote the contribution of p to the prime factorizations of b and d respectively. The greatest power of p to divide b^{2}d^{2}n is p^{2e+2f+g}. So, since g is even, b^{2}d^{2}n cannot be a sum of squares. But it is, so we’ve reached a contradiction. Therefore, n can be expressed as a product of two squares.

5. Claim: An odd prime p is of the form 8m+1 or 8m+3 if and only if it can be written as p = x^{2} + 2y^{2} for some integers x and y. Proof: (⇐) Suppose p = x^{2} + 2y^{2} for integers x and y and odd prime p. Then,

x^{2} + 2y^{2} ≡ 0 (mod p). Since 𝔽_{p} is a field, we can divide by y^{2}: (\frac{x}{y})^{2} ≡ −2 (mod p).

So, we have (\frac{−2}{p}) = 1, that is, −2 is a square modulo p. Using the multiplicativity of

the Kronecker symbol and the formula for (\frac{2}{p}) from Lecture 13, we have:

(\frac{−2}{p}) = (\frac{−1}{p}) (\frac{2}{p}) = (−1)^{(p−1)/2} (\frac{2}{p}) = K.

Now, we examine the four cases of odd p: Case 1: p ≡ 1 (mod 8). Then, K = (1) · (1) = 1. Case 2: p ≡ 3 (mod 8). Then, K = (−1) · (−1) = 1. Case 3: p ≡ 5 (mod 8). Then, K = (1) · (−1) = −1. Contradiction!. Case 4: p ≡ 7 (mod 8). Then, K = (−1) · (1) = −1. Contradiction!. So, assuming p = x^{2} + 2y^{2}, we have concluded that p must be of the form 8m + 1 or 8m + 3. (⇒) From the previous direction, we noticed that if odd prime p is of the 8m + 1 or 8m+3, then −2 is a square modulo p. So there exists an r such that r^{2} ≡ −2 (mod p). Let n = ⌊\sqrt{p}⌋. Now, let’s use Lemma 1.3 from Lecture 21, using x = −\frac{r}{p}. Then, there exist integers a, b such that 0 < b ≤ n < \sqrt{p} such that

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

Let c = rb + pa. Notice that 0 < b^{2} < p^{2}. Then we have,

|c| < \frac{pb}{b\sqrt{p}} = \sqrt{p}.

From this, we can conclude that

0 < 2b^{2} + c^{2} < 3p.

Recalling that c ≡ rb (mod p) and r^{2} ≡ −2, we write

2b^{2} + c^{2} ≡ 2b^{2} + r^{2}b^{2} = b^{2}(2 + r^{2}) ≡ 0 (mod p).

So, either p = 2b^{2} + c^{2} or 2p = 2b^{2} + c^{2}. In the first case, we are done. In the second, divide both sides by 2: p = b^{2} + c^{2}/2. Since p is an integer, c^{2} must be even. Since it is a square, it contains c^{2} = 4d^{2}, where d ∈ ℤ. So p = b^{2} + 2d^{2}, and we are done.

6. Triangular numbers can be expressed using little Gauss’s trick. Namely, T_{m} = \frac{1}{2}(m + 1)m.

(a) 8T_{m}^{2} = (2T_{m})^{2} + (2T_{m})^{2}.

(b) 8T_{m}^{2} + 1 = (m^{2} − 1)^{2} + ((m + 1)^{2} − 1)^{2} = 2m^{4} + 4m_{2}^{3}m^{2} + 1 I found this by finding a pattern over m. It is encapsulated here:

? ?t
t(m) = (1/2)*m*(m+1)
? x=3.0;for(X=2,20,y=sqrt(8*t(X)^2+1-x^2);print([X, x,y]);x=y)
[2, 3.0000, 8.0000]
[3, 8.0000, 15.000]
[4, 15.000, 24.000]
[5, 24.000, 35.000]
[6, 35.000, 48.000]
[7, 48.000, 63.000]
[8, 63.000, 80.000]
[9, 80.000, 99.000]
[10, 99.000, 120.00]
[11, 120.00, 143.00]
[12, 143.00, 168.00]
[13, 168.00, 195.00]
[14, 195.00, 224.00]
[15, 224.00, 255.00]
[16, 255.00, 288.00]
[17, 288.00, 323.00]
[18, 323.00, 360.00]
[19, 360.00, 399.00]
[20, 399.00, 440.00]

The closed form expression is just noticing that each value is one less than a square.

(c) 8T_{m}^{2} + 2 = (m^{2} + m − 1)^{2} + (m^{2} + m + 1)^{2} = 2m^{4} + 4m_{2}^{3}m^{2} + 2 Similarly, I found a pattern:

? x=1.0;for(X=1,20,y=sqrt(8*t(X)^2+2-x^2);print([X,x,y]);x=x+(X+1)*2)
[1, 1.00000000, 3.00000000]
[2, 5.00000000, 7.00000000]
[3, 11.0000000, 13.0000000]

[4, 19.0000000, 21.0000000]
[5, 29.0000000, 31.0000000]
[6, 41.0000000, 43.0000000]
[7, 55.0000000, 57.0000000]
[8, 71.0000000, 73.0000000]
[9, 89.0000000, 91.0000000]
[10, 109.000000, 111.000000]
[11, 131.000000, 133.000000]
[12, 155.000000, 157.000000]
[13, 181.000000, 183.000000]
[14, 209.000000, 211.000000]
[15, 239.000000, 241.000000]
[16, 271.000000, 273.000000]
[17, 305.000000, 307.000000]
[18, 341.000000, 343.000000]
[19, 379.000000, 381.000000]
[20, 419.000000, 421.000000]

The closed form expression was a tad harder to generate. The smaller number is 1 + 4 + 6 + … + 2m. The larger one is two bigger than the smaller. So a closed form expression is: (1 + \frac{2m+4}{2}(m − 1))^{2} + (3 + \frac{2m+4}{2}(m − 1))^{2}, which simplifies correctly.

7. In every sequence of four consecutive integers, one of the integers can be expressed as n = 4m + 3 for some m. (This is clear, because every integer is either 0, 1, 2, or 3 modulo 4.) Let n = p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{k}^{e_{k}}. Since n is odd, each p_{i} is odd and therefore of the form 4m + 1 or 4m + 3 for some m. Suppose that all of the primes of form 4m + 3 have even exponent. Note that (4m + 3)^{2} ≡ 1 (mod 4) and 4m + 1 ≡ 1 (mod 4). Then,

n ≡ p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{k}^{e_{k}} ≡ 1 (mod 4).

But n ≡ 3 (mod 4), so we have a contradiction. One of the prime factors of n has form 4m + 3 and so cannot be expressed as a sum of integer squares.

8. We reduce 13x^{2} + 36xy + 25y^{2} by using the algorithm shown in lecture 23.

Form  Operation Matrix
(13, 36, 25) 2, k = −1 ( \begin{matrix}1 & −1 \\ 0 & 1 \end{matrix} )
(13, 10, 2) 1 ( \begin{matrix}0 & −1 \\ 1 & 0 \end{matrix} )
(2, 2, 1)  2, k = 3 ( \begin{matrix}1 & 3 \\ 0 & 1 \end{matrix} )
(1, −2, 2) 1 ( \begin{matrix}0 & −1 \\ 1 & 0 \end{matrix} )
(1, 0, 1)  2, k = 1 ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} )

So the equivalence matrix is the product of the matrices above, namely,

g = (\begin{matrix}−4 & −3 \\ 3 & 2 \end{matrix})

We omit the same (rather dull) calculation for 58x^{2} + 82xy + 29y^{2} and plug it into Pari, which shows that it is also equivalent to the form (1, 0, 1). For the second part, we note that 389 = 10^{2} + 17^{2}. Then, g multiplied by the column vector (10, 17)^{T} = (−91, 64), which, sure enough, satisfies the equality.

9. The discriminants of both forms are b^{2} − 4ac = −24. The forms, however, are not equivalent. We reduce the forms using PARI:

%10 = -24
? reduce([199,-162,33])
%11 = [1, 0, 6]
? reduce([35,-96,66])
%12 = [2, 0, 3]

We see that the forms are not equivalent, otherwise they would have the same reduced form.