Johnny Chen

Math 124 Problem Set 6

1. -389 is negative, and thus not the sum of two squares. Since $3\vert\vert 12345$, it is not the sum of two squares. Since $7\vert\vert 91210$, it is not the sum of two squares. $729=27^2$ is a perfect square. Since $7\vert\vert 1729$, it is not the sum of two squares. Finally, $151\vert\vert 68252$ and $151\equiv 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\vert\vert n$, where $p\equiv 3(mod\ 4)$ is a prime factor and $r$ is odd. Now, $nb^2d^2=(ad)^2+(bc)^2$, so $nb^2d^2$ is the sum of two integer squares. However, all the prime factors of $b^2d^2$ have even exponent, so $p^s\vert\vert nb^2d^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\equiv 0(mod\ p)$, so $(\frac{x}{y})^2\equiv -2(mod\ p)$ (since $Z_p$ is a field). From Lecture 13, $(\frac{2}{p})=1$ iff $p\equiv \pm1(mod\ 8)$. Also, $(\frac{-1}{p})=1$ iff $p\equiv 1(mod\ 4)\Rightarrow p\equiv 1,-3(mod\ 8)$. Since $(\frac{-2}{p})=(\frac{-1}{p})\cdot (\frac{2}{p})$, we have $(\frac{-2}{p})=1$ iff $p\equiv 1,3(mod\ 8)$.
Conversely, suppose $p\equiv 1,3(mod\ 8)$ is prime. Let $r$ be such that $r^2\equiv -2(mod\ p)$. Taking $n=\lfloor \sqrt{p} \rfloor$ and applying Lemma 1.3 from Lecture 21, there exist integers $a,b$ with $0<b<\sqrt{p}$ such that

$$\left\vert-\frac{r}{p}-\frac{a}{b}\right\vert\leq \frac{1}{b(n+1)}<\frac{1}{b\sqrt{p}}.$$

Let $c=rb+pa$; then $\vert c\vert<\frac{pb}{b\sqrt{p}}=\sqrt{p}$, so $2b^2+c^2<3p$. Since $c\equiv rb(mod\ p)$, we also have that $2b^2+c^2\equiv b^2(2+r^2)\equiv 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\Rightarrow p=b^2+2d^2,$$

as desired.
6. Let $T_m$ be the $m$th 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\equiv -1(mod\ 4)$. Since all odd prime factors are congruent to $\pm 1 (mod\ 4)$, $n$ must have some prime factor $p\equiv -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\cdot 11^2-36\cdot 11\cdot 4+25\cdot 4^2=389$.

9. The discriminants are equal: $-24=162^2-4\cdot 199\cdot 33=96^2-4\cdot 35\cdot 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\leq b\leq 5$).