Expansion of Associated Reduced Quadratic Irrational

From ProofWiki

Jump to: navigation, search

Lemma

Let $\alpha$ be transformed into its integer part and fractional part via:

$\alpha = \left \lfloor {\alpha} \right \rfloor + \dfrac 1{\alpha'}$

Then the resulting quadratic irrational $\alpha'$ is also reduced and associated to $n$.

Let $\alpha = \dfrac{\sqrt n + P} Q$ and $X = \left \lfloor {\alpha} \right \rfloor$

Then we have:

$\dfrac 1 {\alpha'} = \dfrac{\sqrt n - \left({Q X - P}\right)} Q$

Since $\sqrt n$ is irrational, we must have $\dfrac 1 {\alpha'} > 0$.

Since $\dfrac 1 {\alpha'}$ is the fractional part, we know:

$0 < \dfrac 1 {\alpha'} < 1 \implies \alpha' > 1$

Transforming:

	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle \alpha'$	$=$	$\displaystyle \frac Q {\sqrt n - \left({Q X - P}\right)} \cdot \frac {\sqrt n + \left({Q X - P}\right)} {\sqrt n + \left({Q X - P}\right)}$	$\displaystyle $	$\displaystyle $	$\displaystyle $
	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle \frac {\sqrt n + \left({Q X - P}\right)} {\frac 1 Q \left({n - \left({Q X - P}\right)^2}\right)}$	$\displaystyle $	$\displaystyle $	$\displaystyle $

we have $P' = Q X - P$ and $Q' = \dfrac 1 Q \left({n - \left({Q X - P}\right)^2}\right)$.

To show $Q' \in \Z$:

We have that $n - (QX - P)^2 \equiv n - P^2 \bmod Q$, and since $\alpha$ is associated to $n$, $Q$ must divide this quantity.

Hence $Q'$ is an integer as defined.

Since $X = \left \lfloor{\dfrac{\sqrt n + P} Q}\right \rfloor$ is an integer and $\alpha$ is irrational, we know $X < \dfrac {\sqrt n + P} Q$.

Hence $P' = QX - P < \sqrt{n}$ forcing $\tilde{\alpha}' < 0$.

Since $\alpha > 1$ we know $X \ge 1 \iff 0 \le X - 1$.

Thus:

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle \tilde{\alpha}= \frac{P - \sqrt n} Q$	$<$	$\displaystyle 0 \leq X - 1$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle Q$	$<$	$\displaystyle \sqrt n + (QX - P)$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle Q(\sqrt n - (QX - P))$	$<$	$\displaystyle n - (QX - P)^2$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle -\tilde{\alpha}' = \frac{\sqrt n - (QX - P)} {\frac 1 Q \left(n - (QX - P)^2\right)}$	$<$	$\displaystyle 1$	$\displaystyle $	$\displaystyle $	$\displaystyle $

Hence $\tilde{\alpha}' > -1$ and $\alpha'$ is reduced.

Since $Q' = \frac{1}{Q}\left(n - (P')^2\right)$, we know:

$n - (P')^2 \equiv Q Q' \equiv 0 \bmod{Q'}$

Hence $\alpha'$ is associated to $n$.

Thus $\alpha'$ is both reduced and associated to $n$.

$\blacksquare$

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \alpha'\)	\(=\)	\(\displaystyle \frac Q {\sqrt n - \left({Q X - P}\right)} \cdot \frac {\sqrt n + \left({Q X - P}\right)} {\sqrt n + \left({Q X - P}\right)}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {\sqrt n + \left({Q X - P}\right)} {\frac 1 Q \left({n - \left({Q X - P}\right)^2}\right)}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \tilde{\alpha}= \frac{P - \sqrt n} Q\)	\(<\)	\(\displaystyle 0 \leq X - 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle Q\)	\(<\)	\(\displaystyle \sqrt n + (QX - P)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle Q(\sqrt n - (QX - P))\)	\(<\)	\(\displaystyle n - (QX - P)^2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle -\tilde{\alpha}' = \frac{\sqrt n - (QX - P)} {\frac 1 Q \left(n - (QX - P)^2\right)}\)	\(<\)	\(\displaystyle 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)