Exercise 7.8.8 (Least positive solution of $x^2 - 18y^2 = \pm 1$)

Question

Given $\sqrt{18} = \langle 4,\overline{4,8} \rangle$, find the least positive solution of $x^2 - 18 y^2 = -1$ (if any) and of $x^2 - 18 y^2 =1$.

Richard Ganaye · Accepted Answer

\begin{proof} 
Using (7.13),  we obtain
$$m_{i+1} = a_i q_i - m_i,\qquad q_{i+1} = \frac{d-m_{i+1}^2}{q_i}, \qquad a_i = \left \lfloor \frac{m_i + \lfloor \sqrt{d}floor}{q_i}ight floor ,$$
 where $\lfloor \sqrt{d}floor = \lfloor \sqrt{18}floor = 4$,  $m_0 = 0$, $q_0 = 1$,
\begin{align*}
 &m_0 = 0, \qquad q_0 = 1,\qquad a_0 = 4,\
 &m_1 = 4, \qquad q_1 = 2,\qquad a_1 = 4,\
 &m_2 = 4,\qquad q_2 = 1,\qquad a_2 = 8.
\end{align*}
Since $q_2 = 1$, the algorithm is done, which gives 
$$\sqrt{18} = \langle 4,\overline{4,8} angle.$$

Since the length $r = 2$ of the period is even, we know by Theorem 7.25 that $x^2 - 18 y^2 = -1$ is not solvable.

We find the convergents by 7.6:
\begin{center}
\begin{tabular}{c|ccccc}
    $i$& -2 & -1 & 0 & 1 & 2\
\hline
$a_i$ &    &    &  4  & 4 & 8\
$h_i$ & 0 & 1 & 4  & 17&\
$k_i$ & 1 & 0  & 1 & 4  &
\end{tabular}
\end{center}
Since $r = 2$, by Theorem 7.25, the least positive solution of $x^2 - 18 y^2 = 1$ is $(h_{r-1}, k_{r-1}) = (h_1,k_1) = (17,4)$:
$$17^2 - 18 \cdot 4^2 = 1.$$
(See Problem 9 for a Python program).
\end{proof}

Exercise 7.8.8 (Least positive solution of $x^2 - 18y^2 = \pm 1$)

Answers

Comments

$i$	-2	-1	0	1	2

$a_{i}$			4	4	8
$h_{i}$	0	1	4	17
$k_{i}$	1	0	1	4

Exercise 7.8.8 (Least positive solution of $x^2 - 18y^2 = \pm 1$)

Answers

Comments

Add answer