Determine the integers $x$ and $y$ such that $x^2 + y^2 = 178$.
Prime factorisation gives us $178 = 2 \times 89$. By the Sum of Two Squares Theorem (8.5), factors 2 and $89 \equiv 1 \pmod 4$ tells us 178 can be written as a sum of two squares.
Experimenting with small numbers immediately gives us
$$ 178 = 3^2 + 13^2 $$
Show that if $\gcd (x, y) = 1$ and $x^2 + y^2 = z^2$ then $\gcd (x, z) = \gcd (y, z) = 1$.
Let $g=\gcd(x,z)$. This means, that for some integers $x',z'$ we have $x=gx'$ and $z=gz'$. And so
$$ x^2 + y^2 = z^2 \quad \implies \quad g^2(z'^2 - x'^2) = y^2 $$
This means $g$ is a factor of $y$.
But if $g$ is a factor of $y$ and $x$ then $g=1$ since we know $\gcd(x,y)=1$. And so $\gcd(x,z)=1$.
By a symmetric argument $\gcd(y,z)=1$.
And so, the constraints $\gcd (x, y) = 1$ and $x^2 + y^2 = z^2$ imply $\gcd (x, z) = \gcd (y, z) = 1$.
Show the Pythagorean triple identity
$$ (a^2 + b^2)^2 = (a^2 − b^2)^2 + (2ab)^2 $$
by using sum of squares identity.
We remind ourselves of the Conversion Identity (8.1) for the remaining exercises:
$$ (a^2 + b^2) (c^2 + d^2) = (ac− bd)^2 + (ad + bc)^2 $$
By equating $a=c$ and $b=d$, the Conversion Identity immediately gives us
$$ (a^2 + b^2)^2 = (a^2− b^2)^2 + (2ab)^2 $$
This is a question on Pythagorean triples.
Convert the following squares to sum of two non-zero squares:
(a) $5^2$ (b) $17^2$ (c) $29^2$ (d) $202^2$
(a) It is clear that
$$ 5^2 = 3^2 + 4^2 $$
Many people have this Pythagorean triple memorised from school education.
We will use the Conversion Identity (8.1) for the remaining exercises:
$$ (a^2 + b^2) (c^2 + d^2) = (ac− bd)^2 + (ad + bc)^2 $$
(b) We have
$$ 17^2 = (4^2 + 1^2)(4^2 + 1^2) = (16-1)^2 + (4+4)^2 = 15^2 +8^2 $$
(c) We have
$$ 29^2 = (5^2 + 2^2)(5^2 + 2^2) = (25-4)^2 + (10+10)^2 = 21^2 +20^2 $$
(d) We have $202^2=2^2\times 101^2$, and so
$$ 101^2 = (10^2 + 1^2)(10^2 + 1^2) = (100-1)^2 + (10+10)^2 = 99^2 +20^2 $$
And finally,
$$ 202^2 = 2^2 \times (99^2 +20^2 ) = 198^2 + 40^2 $$
Prove the following identity for any integers $a$, $b$, $c$, and $d$:
$$ (a^2 + b^2) × (c^2 + d^2) = (ac + bd)^2 + (ad− bc)^2 $$
This is another sum of squares identity like (8.1).
We expand the LHS:
$$ (a^2 + b^2) × (c^2 + d^2) = a^2c^2 + a^2d^2 + b^2c^2 + b^2d^2 $$
We expand the RHS:
$$ (ac + bd)^2 + (ad− bc)^2 = a^2c^2 + b^2d^2 + \cancel{2abcd} + a^2d^2 + b^2c^2 - \cancel{2abcd} = a^2c^2 + a^2d^2 + b^2c^2 + b^2d^2 $$
The LHS = RHS, and so
$$ (a^2 + b^2) × (c^2 + d^2) = (ac + bd)^2 + (ad− bc)^2 $$
Show that any integer $n > 1$ can be written as $n = p_1 \times p_2 × \ldots × p_r × N^2$ where $p$’s are distinct primes.
By the fundamental theorem of arithmetic, any integer larger than 1 can be written uniquely as a product of primes.
$$ n = p_1^{k_1} \times p_2^{k_2} \times \ldots \times p_x^{k_x}$$
Each prime factors $p_i$ appears $k_i$ times in this product.
There are two cases for $k_i$, even $k_i=2m$ and odd $k_i=2m+1$, for some positive number $m$.
Case $k_i$ even
We can write each prime factor that appears an even number of times as
$$ p_i^{k_i} = p_i^{2m} = (p_i^m)^2 $$
And so each $p_i$, which appears an even number of times in the prime factorisation of $n$, is a factor of $N^2$.
Case $k_i$ odd
Similarly, we can write each prime factor that appears an odd number of times as
$$ p_i^{k_i} = p_i^{2m+1} = p_i \times (p_i^m)^2 $$
And so each $p_i$ which appears an odd number of times in the prime factorisation of $n$, appears once in the product of unique primes, and the remaining even number of $p_i$ are factors of $N^2$.
And so any integer $n>1$ can be written as a product of distinct primes and a perfect square $N^2$.
Prove Lemma (8.2).
Let's remind ourselves of Lemma (8.2).
If prime $p \equiv 1 \pmod 4$ then there exist positive integers $x$ and $y$ such that $x^2 + y^2 = kp$ where $k < p$ and it is a positive integer.
We can write $x^2 + y^2 = kp$ as
$$ x^2 \equiv -y^2 \pmod p $$
Since $p \equiv 1 \pmod 4$, by Proposition (7.11) we have
$$ (\frac{-1}{p}) = 1$$
By definition of the Legendre symbol
$$ (\frac{y^2}{p}) = 1 $$
Using the multiplicity of the Legendre symbol
$$ (\frac{-y^2}{p}) = (\frac{-1}{p}) \times (\frac{y^2}{p}) = 1 \times 1 = 1 $$
But $(\frac{-y^2}{p})=1$ means that the following has integer solutions for $x$,
$$ x^2 \equiv - y^2 \pmod p $$
That is, $x^2 + y^2 = kp$ has solutions.
Because $(-x)^2 = x^2$ and $(-y)^2 = y^2$, we can additionally state that positive integer solutions exist.
We now need to show that $k < p$ still permits solutions.
If $x \pmod p$ is a solution, so is $-x \equiv p-x \pmod p$. This means that if solutions exist, they include solutions in the range $0 \le x < \frac{p}{2}$.
This means
$$ 0 \le x^2 + y^2 < (\frac{p}{2})^2 + (\frac{p}{2})^2 = \frac{p^2}{2} = \frac{p}{2} \times p $$
That is, solutions to $x^2 + y^2 =kp$ exist when $k < \frac{p}{2} < p$.