Cauchy's Lemma (Number Theory)

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a$ and $b$ be odd positive integers.

Suppose $a$ and $b$ satisfy:

$b^2 < 4 a$
$3 a < b^2 + 2 b + 4$

Then there exist non-negative integers $s, t, u, v$ such that:

\(\displaystyle a\) \(=\) \(\displaystyle s^2 + t^2 + u^2 + v^2\)
\(\displaystyle b\) \(=\) \(\displaystyle s + t + u + v\)


Proof

Because $a$ is odd, we can write:

$a = 2 k + 1$

for some positive integer $k$.

Then:

\(\displaystyle 4 a - b^2\) \(=\) \(\displaystyle 4 \paren {2 k + 1} - b^2\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 8 k + 4 - 1\) \(\displaystyle \pmod 8\) Odd Square Modulo 8
\(\displaystyle \) \(\equiv\) \(\displaystyle 3\) \(\displaystyle \pmod 8\)

Because $b^2 < 4 a$, we have that $4 a - b^2$ is a positive integer.

By Integer as Sum of Three Odd Squares, there exist $3$ odd integers $x, y, z$ such that:

$4 a - b^2 = x^2 + y^2 + z^2$


Because $b, x, y, z$ are all odd integers, $b + x + y + z$ must be even.


It is now to be shown that $b + x + y \pm z$ is divisible by $4$.

Suppose that $b + x + y + z$ is not divisible by $4$.

Because $b + x + y + z$ is even:

$b + x + y + z \equiv 2 \pmod 4$

Writing $z = 2 l + 1$:

\(\displaystyle b + x + y - z\) \(=\) \(\displaystyle b + x + y + z - 2 z\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 2 - 2 \paren {2 l + 1}\) \(\displaystyle \pmod 4\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 2 - 4 l - 2\) \(\displaystyle \pmod 4\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 0\) \(\displaystyle \pmod 4\)

That is:

if $b + x + y + z$ is not divisible by $4$
then $b + x + y - z$ is divisible by $4$.

$\Box$


Let us choose the case such that $b + x + y \pm z$ is divisible by $4$.

We define:

\(\displaystyle s\) \(=\) \(\, \displaystyle \frac {b + x + y \pm z} 4 \, \) \(\displaystyle \)
\(\displaystyle t\) \(=\) \(\, \displaystyle \frac {b + x - y \mp z} 4 \, \) \(\, \displaystyle = \, \) \(\displaystyle \frac {b + x} 2 - s\)
\(\displaystyle u\) \(=\) \(\, \displaystyle \frac {b - x + y \mp z} 4 \, \) \(\, \displaystyle = \, \) \(\displaystyle \frac {b + y} 2 - s\)
\(\displaystyle v\) \(=\) \(\, \displaystyle \frac {b - x - y \pm z} 4 \, \) \(\, \displaystyle = \, \) \(\displaystyle \frac {b \pm z} 2 - s\)

We are to show that $s, t, u, v$ are non-negative, and will satisfy:

\(\text {(1)}: \quad\) \(\displaystyle a\) \(=\) \(\displaystyle s^2 + t^2 + u^2 + v^2\)
\(\text {(2)}: \quad\) \(\displaystyle b\) \(=\) \(\displaystyle s + t + u + v\)


First we show that $s, t, u, v$ are non-negative.

Because $x, y, z$ are positive:

$s, t, u, v \ge \dfrac {b - x - y - z} 4$

So we need to show:

$\dfrac {b - x - y - z} 4 \ge 0$

or equivalently:

$\dfrac {b - x - y - z} 4 > -1$


Now:

\(\displaystyle x + y + z\) \(=\) \(\displaystyle \sqrt {\paren {x + y + z}^2}\)
\(\displaystyle \) \(=\) \(\displaystyle \sqrt {x^2 + y^2 + z^2 + 2 x y + 2 y z + 2 z x}\)
\(\displaystyle \) \(\le\) \(\displaystyle \sqrt {x^2 + y^2 + z^2 + 2 \paren {\sqrt {x^2 + y^2 + z^2} } \paren {\sqrt {y^2 + z^2 + x^2} } }\) Cauchy's Inequality
\(\displaystyle \) \(=\) \(\displaystyle \sqrt {3 \paren {x^2 + y^2 + z^2} }\)
\(\displaystyle \) \(=\) \(\displaystyle \sqrt {3 \paren {4 a - b^2} }\) $4 a - b^2 = x^2 + y^2 + z^2$
\(\displaystyle \) \(<\) \(\displaystyle \sqrt {4 \paren {b^2 + 2 b + 4} - 3 b^2}\) $3 a < b^2 + 2 b + 4$
\(\displaystyle \) \(=\) \(\displaystyle \sqrt {b^2 + 8 b + 16}\)
\(\displaystyle \) \(=\) \(\displaystyle b + 4\) Square of Sum
\(\displaystyle \leadsto \ \ \) \(\displaystyle \frac {b - x - y - z} 4\) \(>\) \(\displaystyle -1\)

showing that $s, t, u, v$ are non-negative.


Now we check $(1)$:

\(\displaystyle s^2 + t^2 + u^2 + v^2\) \(=\) \(\displaystyle \paren {\frac {b + x + y \pm z} 4}^2 + \paren {\frac {b + x - y \mp z} 4}^2 + \paren {\frac {b - x + y \mp z} 4}^2 + \paren {\frac {b - x - y \pm z} 4}^2\)
\(\displaystyle \) \(=\) \(\displaystyle \frac 1 {16} ( b^2 + x^2 + y^2 + z^2 + 2 b x + 2 b y \pm 2 b z + 2 x y \pm 2 x z \pm 2 y z\)
\(\displaystyle \) \(\) \(\displaystyle + \quad b^2 + x^2 + y^2 + z^2 + 2 b x - 2 b y \mp 2 b z - 2 x y \mp 2 x z \pm 2 y z\)
\(\displaystyle \) \(\) \(\displaystyle + \quad b^2 + x^2 + y^2 + z^2 - 2 b x + 2 b y \mp 2 b z - 2 x y \pm 2 x z \mp 2 y z\)
\(\displaystyle \) \(\) \(\displaystyle + \quad b^2 + x^2 + y^2 + z^2 - 2 b x - 2 b y \pm 2 b z + 2 x y \mp 2 x z \mp 2 y z )\)
\(\displaystyle \) \(=\) \(\displaystyle \frac 1 {16} \paren {4 \paren {b^2 + x^2 + y^2 + z^2} }\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {4 a} 4\)
\(\displaystyle \) \(=\) \(\displaystyle a\)


Now we check $(2)$:

\(\displaystyle s + t + u + v\) \(=\) \(\displaystyle \frac {b + x + y \pm z} 4 + \frac {b + x - y \mp z} 4 + \frac {b - x + y \mp z} 4 + \frac {b - x - y \pm z} 4\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {4 b} 4 + \frac {2 x - 2 x} 4 + \frac {2 y - 2 y} 4 \pm \frac {2 z - 2 z} 4\)
\(\displaystyle \) \(=\) \(\displaystyle b\)

Therefore $s, t, u, v$ as defined are the integers we are looking for.

$\blacksquare$


Source of Name

This entry was named for Augustin Louis Cauchy.


Sources