%%
%% This file is to distribute at ac99.
%% This file should be compiled by pLaTeX2e with AMS-LaTeX 1.2
%%
\documentclass[11pt,twoside]{jarticle}
\usepackage{amsmath,amssymb}
\usepackage{amsthm}

\title{������Ostrowskiɽ����\\ 2��2�������������ε��ˤĤ���}
\author{���� ε��\ ��̾�Ų���ؿʹ־���DC��}
\date{1999(ʿ��11)ǯ10��20��\\
      ������3�������ؤȷ׻��׸��潸���AC99�ˡ������Ω��ء�}

\pagestyle{myheadings}
\markboth{\textrm{��3�������ؤȷ׻��׸��潸��\ �ֱ��ѻ���}}%
         {\textrm{1999��ʿ��11��ǯ10��20��, ����ε��}}         
\allowdisplaybreaks

\theoremstyle{definition}
\newtheorem{theorem}{����}
\newtheorem{proposition}{̿��}
\newtheorem{lemma}{����}
\newtheorem{assume}{����}
\newtheorem{algorithm}{���르�ꥺ��}
\newtheorem{example}{��}


\begin{document}
\maketitle
\tableofcontents

\begin{abstract}
���������� $x^2 - D y^2 = N$ �β��ü�ʷ���ɽ���Ǥ���Ȥ������Ȥ�
Rockett��Sz\"usz�ˤ���ĥ���줿��\cite{RocSzu86}, \cite{RocSzu}��.
�����, ����������ľ��,
���������륢�르�ꥺ��μ¸��˱��Ѥ��뤳�ȤˤĤ�����𤹤�.
\end{abstract}


\section{$\sqrt{D}$ ��Ϣʬ��Ÿ���ȸ�ŵŪ����}

$D$ ��ʿ�����ǤϤʤ��������Ȥ���.
$\sqrt{D}$ ��Ϣʬ��Ÿ��
\begin{equation}
\sqrt{D} = a_0 + \frac1{a_1+} \frac1{a_2+} \cdots
\end{equation}
�ˤ����Ƥ�,
��ʬ�� $a_n$ �� $a_0$ ������Ƽ���Ū�Ǥ��뤳�Ȥ��Τ��Ƥ���.
������, ���μ�����Ĺ���� $l$ �Ȥ���.
���ΤȤ�, ��������Ω�Ĥ��Ȥ��Τ��Ƥ���:
\begin{gather}
a_{nl} = 2 a_0 \quad\text{($n$ ��������)}, \\
a_t = a_{l-t} \quad\text{($1 \le t < l$)}
\end{gather}

������ $\{p_n\}_{n \ge -1}$, $\{q_n\}_{n \ge -1}$ �򼡤��������:
\begin{alignat}{4}
p_{-1} &= 1, &\quad
p_0 &= a_0, &\quad
p_n &= a_n p_{n-1} + p_{n-2} &\quad& \text{($n \ge 1$)}; \\
q_{-1} &= 0, &
q_0 &= 1, &
q_n &= a_n q_{n-1} + q_{n-2} && \text{($n \ge 1$)}.
\end{alignat}

\begin{example}
$\sqrt{61}$ ��Ϣʬ��Ÿ��.
\begin{gather*}
\sqrt{61}
 = 7+\underbrace{
     \frac1{1+}\frac1{4+}\frac1{3+}\frac1{1+}\frac1{2+}%
     \frac1{2+}\frac1{1+}\frac1{3+}\frac1{4+}\frac1{1+}\frac1{14+}
   }_{\text{repeat}}\\
\begin{array}{|c||*{11}{r|}} \hline
n   & 0 & 1 &  2 &   3 &   4 &   5 &    6 &    7 &    8 &     9 &    10 \\
\hline\hline
p_n & 7 & 8 & 39 & 125 & 164 & 453 & 1070 & 1523 & 5639 & 24079 & 29718 \\
q_n & 1 & 1 &  5 &  16 &  21 &  58 &  137 &  195 &  722 &  3083 &  3805 \\
\hline
\end{array}
\end{gather*}
\qed
\end{example}

$N$ ��Ǥ�դ������Ȥ���.
���������� $x^2 - D y^2 = N$ �� $\sqrt{D}$ ��Ϣʬ��Ÿ���Ȥ�
��Ϣ������¤Ȥ���, ���Τ��Ȥ��褯�Τ��Ƥ���:
\begin{proposition}
$D$ ��ʿ�����ǤϤʤ��������Ȥ���.
$x^2 - D y^2 = \pm1$ ��������������,
$(x,y) = (p_{ml-1},q_{ml-1})$ ($m>0$)�����Τ��٤ƤǤ���.
�����, ��������Ω��:
$$
{p_{ml-1}}^2 - D {q_{ml-1}}^2 = (-1)^{ml}.
$$
�Ȥ���, $x^2 - D y^2 = -1$ ���Ĳ�Ǥ��뤳�Ȥ�,
$\sqrt{D}$ ��Ϣʬ��Ÿ���μ��� $l$ ������Ǥ��뤳�ȤȤ�,
Ʊ�ͤǤ���.
\qed
\end{proposition}

\begin{proposition}
$D$ ��ʿ�����ǤϤʤ�������, $N$ ��Ǥ�դ������Ȥ���.
$x^2 - D y^2 = N$ ��, �������1�ĤǤ���Ƥ�, ̵�¸Ĥ�����������.
�����, ������¸�ߤ����,
$0 < y < q_{l-1}\sqrt{|N|}$ �ʤ�������¸�ߤ���
\qed
\end{proposition}
���λ��¤ˤĤ��Ƥ�, �����ΰ㤤�Ϥ��뤬,
���Ȥ��й���\cite{Takagi}��3�Ϥ򻲾ȤΤ���.

\begin{proposition}
$D$ ��ʿ�����ǤϤʤ���������,
$N$ �� $|N|<\sqrt{D}$ �ʤ������Ȥ���.
���ΤȤ�, $x^2 - D y^2 = N$ �����������\
$(x,y) = (c p_n, c q_n)$ �ʤ�������.
������ $c$ ��������.
\qed
\end{proposition}


\section{������Ostrowskiɽ��}

$\{q_n\}$ �ˤĤ��Ƥϼ�������Ω�Ĥ��Ȥ����դƤ���:
\begin{equation}
1 = q_0 \le q_1 < q_2 < q_3 < \cdots.
\end{equation}

$y$ ���������Ȥ���.
$q_n \le y < q_{n+1}$ �������� $n$ ����դ�¸�ߤ���.
������, $y = c_{n+1} q_n + y'$, $0 \le y' < q_n$ ��������
���� $c_{n+1}$, $y'$ �����Ū��¸�ߤ���.
$y' \ne 0$ �ʤ��, $q_{n'} \le y < q_{n'+1}$ �ʤ� $n'$ ��,
������, $y' = c_{n'+1} q_{n'} + y''$, $0 \le y'' < q_{n'}$ ��������
���� $c_{n'+1}$, $y''$ ��, ���Ū��¸�ߤ���.
����򷫤��֤���, �Ĥ��ˤϤ�������λ��,
$q_k$ �ΰ켡���Ȥ��Ƥ� $y$ ��ɽ��
\begin{equation}\label{eq:OstrowskiRep}
y = \sum_{k=0}^{n} c_{k+1} q_k
\end{equation}
��������.
������, $\{c_{k+1}\}$ �ϼ����������Ƥ��뤳�Ȥ��狼��:
\begin{itemize}
\item $0 \le c_{k+1} \le a_{k+1}$ ($k \ge 1$), $0 \le c_1 < a_1$;
\item $c_{k+1} = a_{k+1}$ �ʤ�� $c_k = 0$.
\end{itemize}
�����, ��Τ褦�ʷ��������������켡���Ȥ��Ƥ� $y$ ��ɽ����
���Ū����ޤ뤳�Ȥ��ǧ���뤳�Ȥ��Ǥ���.
�����, $y$ �� $\sqrt{D}$ �˴ؤ���Ostrowskiɽ���ȸƤ֤��Ȥˤ��褦.


\section{������Ostrowskiɽ���������������β�}
\label{sec:Ost_of_sol}

$(x,y)$ �� $x^2 - D y^2 = N$ ����������Ǥ���Ȥ���.
$y$ ����ʬ�礭���ΤǤ����,
$y$ �� $\sqrt{D}$ �˴ؤ���Ostrowskiɽ���ˤ�����\
$q_n$ �� $p_n$ ���֤���������Τ� $x$ �����������Ȥ��狼��.
������Τˤ�, ��������������Ω�ġ�\cite{Hashimoto1}��.
%
\begin{theorem}\label{thm:sol1}
$D$ ��ʿ�����ǤϤʤ�������, $N$ �������Ǥ���Ȥ���.\\
$\epsilon = \min\bigl(\sqrt{D}-a_0,
1/(2\sqrt2), (1+a_0-\sqrt{D})/\sqrt2 \bigr)$ �Ȥ���.
\par
$(x,y)$ �� $x^2 - D y^2 = N$ ����������Ǥ���,
$y > |N|/(2\epsilon\sqrt{D})$ �ʤ��,
$x$, $y$ �ϼ��η���ɽ�蘆���:
\begin{align*}
x &= c_{n+1} p_n + c_{n+2} p_{n+1} + \cdots + c_{n+m} p_{n+m-1}, \\
y &= c_{n+1} q_n + c_{n+2} q_{n+1} + \cdots + c_{n+m} q_{n+m-1}.
\end{align*}
%������ $y$ �� $\sqrt{D}$ �˴ؤ���Ostrowskiɽ����ɽ�蘆��Ƥ���.
������, ���� $c_{k+1}$ �ϼ��ξ���������:
\begin{itemize}
\item
$c_{n+1} \ne 0$, $c_{n+m} \ne 0$;
\item
$0 \le c_{k+1} \le a_{k+1}$ ($k \ge 1$), $0 \le c_1 < a_1$;
\item
$c_{n+1} = a_{n+1}$ �ʤ�� $c_n = 0$.
\end{itemize}
������, $N>0$ �ʤ�� $n$ �ϴ���Ǥ���, $N<0$ �ʤ�� $n$ �϶����Ǥ���.
\qed
\end{theorem}

\begin{example}
$x^2 - 61 y^2 = 611$.
$(x,y) = (202546892400,25933472143)$ �ϲ�Ǥ���,
\begin{align*}
202546892400 &= 5 p_{21} + 2 p_{23} + p_{24}, \\
 25933472143 &= 5 q_{21} + 2 q_{23} + q_{24}.
\end{align*}
�Ȥ�����, $(x,y) = (60,7)$ ���Ǥ���,
$y = 7$ �� $\sqrt{61}$ �˴ؤ���Ostrowskiɽ����
$7 = 2 q_1 + q_2$ �Ǥ��뤬, $60 \ne 2 p_1 + p_2 = 55$.
\end{example}


\section{�������ɽ����Ĺ����ɾ��}

������Ǥϼ��Τ��Ȥ��ꤹ��:
\begin{assume}
$x^2 - Dy^2 = N$ ���������� $(x,y)$ �����η���ɽ�蘆���:
\begin{align*}
x &= c_{n+1} p_n + c_{n+2} p_{n+1} + \cdots + c_{n+m} p_{n+m-1}, \\
y &= c_{n+1} q_n + c_{n+2} q_{n+1} + \cdots + c_{n+m} q_{n+m-1}.
\end{align*}
������, $n \ge 0$, $m > 0$ �Ǥ���,
���� $c_{k+1}$ �ϼ��ξ���������:
\begin{itemize}
\item
$c_{n+1} \ne 0$, $c_{n+m} \ne 0$;
\item
$0 \le c_{k+1} \le a_{k+1}$ ($k \ge 1$), $0 \le c_1 < a_1$;
\item
$c_{n+1} = a_{n+1}$ �ʤ�� $c_n = 0$.
\qed
\end{itemize}
\end{assume}

���β���β���, ��������¤�Ĺ�� $m$ �� %
$D$ �� $N$ �ˤ��ɾ������뤳�Ȥ��狼��.
��������ˤ��, ����ɾ���������Ū�˽񤭲������Ȥ��Ǥ���:
\begin{lemma}
����β���, ��������Ω��:
$$
\frac{|N|-(2/{q_n}^2)}{2\sqrt{D}} < \frac{q_{n+m-1}}{q_{n-1}};\quad
%\text{$m\ge3$ �ʤ��}\quad
\frac{q_{n+m-3}}{q_{n}} < \frac{|N|+(2/{q_n}^2)}{\sqrt{D}}.
$$
\qed
\end{lemma}

��������ȸ�˽Ҥ٤�����\ref{thm:period1}�Ȥ��Ȥ߹�碌�뤳�Ȥ�,
�������Ȥ��Ƽ��Τ��Ȥ��狼��:
\begin{theorem}\label{thm:m1}
�¤�Ĺ�� $m$ �ϼ��Τ褦��ɾ�������:
\begin{multline*}
\frac1{\log(1+a_0) + (\log2)/l} \cdot \log\frac{|N|}{4\sqrt{D}} \\
< m
< \max\left(
    3, 3 + \log_{\tau}\sqrt5 + \log_{\tau}\frac{|N|}{\sqrt{D}}
  \right).
\end{multline*}
������, $\tau = (1+\sqrt5)/2$.
\qed
\end{theorem}
����ɾ�����ϲ��ɤ�;�Ϥ��礭��.
�Ȥ���, Ϣʬ��Ÿ���η�������Ū�ˤ狼�äƤ������,
���褤ɾ������񤭲������Ȥ��Ǥ���.
���Ȥ���, $l=1$ �ξ���ͤ��Ƥߤ�.
���ΤȤ��� $a_k = 2 a_0$ ($k \ge 1$), $D = {a_0}^2 + 1$ �Ǥ���,
$$
\frac1{\log(1+2a_0)} \cdot \log\frac{|N|}{2\sqrt{D}}
< m
< \max\left(
    3, 3 + \log_{\lambda}\frac{|N|}{a_0}
  \right).
$$
������Ω��.
������, $\lambda = a_0 + \sqrt{{a_0}^2+1}$.


�ºݤη׻��Ǥ�, �����ñ��ʷϤǤ��뼡�μ��������ɤ�ɾ����Ϳ����:
\begin{theorem}\label{thm:m2}
$$
\frac{|N|-2}{2\sqrt{D}} < \frac{q_{n+m-1}}{q_{n-1}};\quad
\frac{q_{n+m-3}}{q_{n}} < \frac{|N|+2}{\sqrt{D}}.
$$
\qed
\end{theorem}


\section{�����������ΰ��̲�}

��ʬ�礭��������ʤ���¹�Ū��ɽ������Ĥ�,
��������ˤĤ��Ƥ�ɬ�����⤽���ǤϤʤ����Ȥ�
\ref{sec:Ost_of_sol}��ǳ�ǧ����.
��δ֤��Ը�ʿ�������Ƥ���ΤǤ���.
�Ȥ�����, ��������������Ω��:
\begin{theorem}\label{thm:period1}
$n>0$, $m>0$ �Ȥ���. ����2�Ĥ�Ʊ�ͤǤ���.
\begin{enumerate}
\renewcommand{\labelenumi}{(\theenumi)}
\item
���� $(x,y)$ �� $x^2-Dy^2=N$ ��������Ǥ���:
\begin{align*}
x &= c_{n+1} p_n + c_{n+2} p_{n+1} + \cdots + c_{n+m} p_{n+m-1}, \\
y &= c_{n+1} q_n + c_{n+2} q_{n+1} + \cdots + c_{n+m} q_{n+m-1}
\end{align*}
\item
���� $(x,y)$ �� $x^2-Dy^2=(-1)^l N$ ��������Ǥ���:
\begin{align*}
x &= c_{n+1} p_{n+l} + c_{n+2} p_{n+1+l}
     + \cdots + c_{n+m} p_{n+m-1+l}, \\
y &= c_{n+1} q_{n+l} + c_{n+2} q_{n+1+l}
     + \cdots + c_{n+m} q_{n+m-1+l}
\end{align*}
\qed
\end{enumerate}
\end{theorem}
�Ĥޤ�, $p_k$, $q_k$ ��ź�� $k$ �򤹤٤ư��Ƥ� $l$ �������餷����Τ�
�ʹ�����̣�ǡ�Ʊ�������������β�ˤʤäƤ���Ȥ������ȤǤ���.
�����Ǥ���ʤ��, $k<0$ �ʤ� $p_k$, $q_k$ �˰�̣��������뤳�Ȥ��Ǥ����,
��δ֤��Ը�ʿ��ʤ������Ȥ��Ǥ���ΤǤϤʤ���������.
���ʤ��, ���٤Ƥ�������
�¹�Ū��ɽ������Ĥ褦�ˤ��뤳�Ȥ��Ǥ���ΤǤϤʤ���������.

����\ref{thm:period1}��,
���μ�������Ω�Ĥ��Ȥ����ưפ˾��������:
$$
\pmatrix p_{k+l} \\ q_{k+l} \endpmatrix
 = \pmatrix p_{l-1} & D q_{l-1} \\ q_{l-1} & p_{l-1} \endpmatrix
   \pmatrix p_{k} \\ q_{k} \endpmatrix
\quad\text{($k>0$)}
$$
������, $n<0$ �ΤȤ��� $p_n$, $q_n$ ��,
���μ��ˤ�굢ǼŪ��������Ƥ��ޤ���.
���������, ��������������Ω�Ĥ��Ȥ��ưפˤ狼��:
\begin{theorem}\label{thm:period2}
����\ref{thm:period1}��Ǥ�դ����� $n$ ����Ω����.
\qed
\end{theorem}

�����, $n<0$ �ΤȤ��� $a_n$ �򼡤�������褦:
$$
a_n = a_{ml+n} \quad\text{for $m \gg 0$}.
$$
���ΤȤ�, �������꤬��ǧ�����:
\begin{lemma}\label{lemma:index<0}
Ǥ�դ����� $n$ �ˤĤ���, ������Ω����:
\begin{gather*}
p_n = a_n p_{n-1} + p_{n-2},\quad
q_n = a_n q_{n-1} + q_{n-2} \quad\text{($n \ne 0$)}, \\
p_0 = 2 a_0 p_{-1} + p_{-2},\quad
q_0 = 2 a_0 q_{-1} + q_{-2} \\
a_{-n} = a_{n},\quad
p_{-n} = (-1)^{n-1} p_{n-2},\quad
q_{-n} = (-1)^n q_{n-2}.
\end{gather*}
\qed
\end{lemma}

\begin{example}
$\sqrt{61}$ �ξ��.
\begin{gather*}
\begin{array}{|c||*{11}{r|}} \hline
n   & -1 & -2 & -3 &  -4 &  -5 &   -6 &  -7 &    -8 &   -9 &   -10 \\
\hline\hline
p_n &  1 & -7 &  8 & -39 & 125 & -164 & 453 & -1070 & 1523 & -5639 \\
q_n &  0 &  1 & -1 &   5 & -16 &   21 & -58 &   137 & -195 &   722 \\
\hline
\end{array}
\end{gather*}
\qed
\end{example}

����\ref{thm:sol1}��\ref{thm:period2}���Ȥ߹�碌�뤳�Ȥ�,
���Τ��Ȥ��狼���\cite{Hashimoto2}��:
\begin{theorem}\label{thm:sol2}
$D$ ��ʿ�����ǤϤʤ�������, $N$ ���������Ǥ���Ȥ���.
\par
$(x,y)$ �� $x^2 - D y^2 = N$ ��������Ǥ���Ȥ���.
������, $N>0$ �ʤ�� $x>0$, $N<0$ �ʤ�� $y>0$ ��
���ꤷ�Ƥ�������򼺤�ʤ�
�ʤ���ʤ���, $(x,y)$ ������� $(-x,-y)$ ��Ȥ�Ф褤��.
\par
���ΤȤ�, $x$, $y$ �ϼ��η��ǰ��Ū��ɽ�蘆���:
\begin{align*}
x &= c_{n+1} p_n + c_{n+2} p_{n+1} + \cdots + c_{n+m} p_{n+m-1}, \\
y &= c_{n+1} q_n + c_{n+2} q_{n+1} + \cdots + c_{n+m} q_{n+m-1}.
\end{align*}
������, ���� $c_{k+1}$ �ϼ��ξ���������:
\begin{itemize}
\item
$c_{n+1} \ne 0$, $c_{n+m} \ne 0$;
\item
$0 \le c_{k+1} \le a_{k+1}$ ($k \ne -1$), $0 \le c_0 \le 2 a_0$;
\item
$c_{k+1} = a_{k+1}$ �ʤ�� $c_k = 0$.
\end{itemize}
\par
�����, $n>0$ �ʤ��, �ʲ��Τ��Ȥ�����Ω��:
$$
\frac{|N|-2}{2\sqrt{D}} < \frac{q_{n+m-1}}{q_{n-1}};\quad
\frac{q_{n+m-3}}{q_{n}} < \frac{|N|+2}{\sqrt{D}}.
$$
\qed
\end{theorem}
������, ���Ȥ� $y>0$ �Ǥ��äƤ� $n>0$ �Ȥϸ¤�ʤ�.
�Ĥޤ�, $y$ ��ɽ���Ϥ�Ϥ� $\sqrt{D}$ �˴ؤ���
Ostrowskiɽ���Ǥ���ȤϤ����ʤ�.
������, ��������Ϥ��������ˤ���褦�ʲ��ɽ����,
�������Ostrowskiɽ���ȸƤ֤��Ȥˤ��褦.

\begin{example}
$x^2 - 61 y^2 = 611$ �β� $(x,y) = (60,7)$ �ˤĤ��Ƥ�,
\begin{align*}
60 &= 5 p_{-1} + 2 p_{1} + p_{2}, \\
 7 &= 5 q_{-1} + 2 q_{1} + q_{2}.
\end{align*}
�Ȥ�����, $(x,y) = (60,-7)$ ���Ǥ��뤬,
����ˤĤ��Ƥϼ���ɽ�������:
\begin{align*}
60 &= p_{-5} + 2 p_{-4} + p_{-3} + 5 p_{-1}, \\
-7 &= q_{-5} + 2 q_{-4} + q_{-3} + 5 q_{-1}.
\end{align*}
\end{example}

����\ref{thm:sol2}������\ref{thm:period2}���,
���Τ��Ȥ��狼��:
\begin{theorem}\label{thm:set}
$x^2 - D y^2 = N$ ����������Ĥ��Ȥ�,
$x^2 - D y^2 = N$ �� $y \in S$ �ʤ���������Ĥ��ȤȤ�Ʊ�ͤǤ���.
������,
$$
S = \left\{ \left. \sum_{k=1}^m c_{n+k} q_{n+k-1}
      \ \right|\  \text{$n$, $m$, $\{c_{n+k}\}$ �ϰʲ��ξ���������}
    \right\}.
$$
\subparagraph{���}
\begin{enumerate}
\item
$l$ �������ʤ�� $0 \le n < l$,
$l$ ������ʤ�� $0 \le n < 2 l$.
\item
$N>0$ �ʤ�� $n$ �ϴ��, $N<0$ �ʤ�� $n$ �϶���.
\item
$c_{n+1} \ne 0$, $c_{n+m} \ne 0$.
\item
$0 \le c_{n+k} \le a_{n+k}$.
\item
$c_{n+k+1} = a_{n+k+1}$ �ʤ�� $c_{n+k} = 0$.
\item
$\dfrac{|N|-2}{2\sqrt{D}} < \dfrac{q_{n+m-1}}{q_{n-1}}$;
$\dfrac{q_{n+m-3}}{q_{n}} < \dfrac{|N|+2}{\sqrt{D}}$.
\qed
\end{enumerate}
\end{theorem}


\section{���Υ��르�ꥺ��}

����\ref{thm:set}���Ȥˤ���,
$x^2 - D y^2 = N$ �βĲ�����Ƚ�����Ū�Ȥ��륢�르�ꥺ���
���ۤ��뤳�Ȥ��Ǥ���.
�ʲ��ˤ��γ��פ򼨤�.

\begin{enumerate}
\renewcommand{\labelenumi}{Step~\theenumi.}
\renewcommand{\theenumii}{\arabic{enumii}}
\renewcommand{\labelenumii}{\theenumi.\theenumii.}
\renewcommand{\theenumiii}{\arabic{enumiii}}
\renewcommand{\labelenumiii}{\theenumi.\theenumii.\theenumiii.}
\renewcommand{\theenumiv}{\arabic{enumiv}}
\renewcommand{\labelenumiv}{%
  \theenumi.\theenumii.\theenumiii.\theenumiv.%
}
\item �ʲ�����, $\sqrt{D}$ ��Ϣʬ��Ÿ����\
$l$, $\{a_n\}$, $\{p_n\}$, $\{q_n\}$ ����Ƥ���;
\item
$0 \le n \le l-1$ �ʤ�� $n$ �ˤĤ���, Step3��5��¹Ԥ���
\item
$m_{\text{max}} := \max\left\{ 3, \max\left\{
 m \ \left|\  \dfrac{q_{n+m-3}}{q_{n}} < \dfrac{|N|+2}{\sqrt{D}} \right.
 \right\}\right\}$;
\item[]
$m_{\text{min}} := \min\left\{
 m \ \left|\  \dfrac{|N|-2}{2\sqrt{D}} < \dfrac{q_{n+m-1}}{q_{n-1}} \right.
 \right\}$;
\item[]
������, Step~3�ˤ����Ƥ� $n=0$ �ΤȤ��Τ� $n=l$ ��Ŭ�Ѥ���.
\item
$m_{\text{min}} = 1$ �ʤ�� $x := p_n$, $y := q_n$;
\item[]
$m_{\text{min}} > 1$ �ʤ�� %
 $x := p_n + p_{n+m_{\text{min}}-1}$,
 $y := q_n + q_{n+m_{\text{min}}-1}$;
\item[]
$m := m_{\text{min}}$.
\item
while $m \ge m_{\text{max}}$,
  \begin{enumerate}
  \item
  $(x,y)$ �ϲ�Ǥ��뤫��Τ����;
  \item\label{alg:add}
  $x := x + (p_n\ \text{or}\ p_{n-1})$;
  $y := y + (q_n\ \text{or}\ q_{n-1})$;
  \item[]
  $y \ge q_{n+m}$ �ʤ�� $m := m + 1$;
  \end{enumerate}
\end{enumerate}

�ʤ�, ���Υץ�������PARI-GP��˼¸�������Τ�, ���θ��潸���,
AC99��FTP�����Ȥ���ӹֱ�Ԥ������Ǥˤ������󶡤����Τ�,
���르�ꥺ��ξܺ٤ˤĤ��ƤϤ�����򻲾Ȥ��줿��.
�ޤ�, ���ƥå�5.2�ˤĤ��Ƥ�,
�ץ������Υ������ޤ��϶���\cite{jssac99}��ϿA�Ϥ򻲾ȤΤ���.


\section{�׻���Ψ}

̿��2�ˤ����õ���������,
����Υ��르�ꥺ��ʤ��ʤ������\ref{thm:set}�ˤˤ��
���õ��������Ȥ�,
$D=61$ �ξ��˲�θ���θĿ�����Ӥ�����Τ�����ɽ�Ǥ���.
\begin{center}
\begin{tabular}{|r||*{5}{r|}}\hline
$|N|$ &   $100$ &   $1001$ &  $10001$ &  $100001$ & $1000000$ \\ \hline\hline
\vbox{\hbox{̿��2�ˤ��}\hbox{��θ���θĿ�}}
      & $38049$ & $120384$ & $380519$ & $1203253$ & $3805000$ \\ \hline
\vbox{\hbox{����\ref{thm:set}�ˤ��}\hbox{��θ���θĿ�}}
      &    $70$ &    $812$ &  $10108$ & $ 788942$ & $4157790$ \\ \hline
\end{tabular}
\end{center}
\cite{jssac99}�ˤ�Ʊ�ͤ�ɽ���Ǻܤ���Ƥ��뤬,
���르�ꥺ��β���, �Ȥ��� $m$ ��ɾ���˴ؤ�����ɤ�ä������Ȥˤ��,
�����������θ��䤬���ʤ��ʤäƤ���.
����ˤ��Ƥ�, $D$ ����٤� $|N|$ ���礭���Ȥ��ˤ�,
�׻���Ψ�����Ǥ��ɤ����르�ꥺ��ȤϤ����ʤ����Ȥ�����������.


\appendix
\section{�ץ������μ¹���}

�ֱ�Ԥˤ��ץ�������PARI-GP��Ǽ¹Ԥ�����򼨤�.

�ץ�����ब��\texttt{program.gp}�פȤ����ե�����̾��
��¸����Ƥ���Ȥ���.
PARI-GP��ư����, ���Υե�������ɤ߹���.
\footnote{%
PARI-GP~2.0.17 (beta)���ɤ߹��������
�㴳�Υ��顼��å����������Ϥ���뤬,
�ؿ�\texttt{ac99}����Ѥ���ʬ�ˤ�����ʤ�.
}
{\footnotesize
\begin{verbatim}
prompt% gp
                    GP/PARI CALCULATOR Version 2.0.11 (beta)
                 UltraSparc (MicroSparc kernel) 32-bit version
                  (readline enabled, extended help available)

                           Copyright (C) 1989-1998 by
          C. Batut, K. Belabas, D. Bernardi, H. Cohen and M. Olivier.

Send bug reports, suggestions and patches to pari@math.u-bordeaux.fr
Type ? for help.

   realprecision = 28 significant digits
   seriesprecision = 16 significant terms
   format = g0.28

parisize = 4000000, primelimit = 500000, buffersize = 30000
? \r program.gp
?
\end{verbatim}
}

���õ���ؿ��ˤϡ�\texttt{ac99}�פȤ���̾����Ĥ��Ƥ���.
$x^2 - 61 y^2 = 611$ �β��õ�����ˤ�,
\underline{\texttt{ac99(61,611)}}�����Ϥ���.
{\footnotesize
\begin{verbatim}
? ac99(61,611)
%1 = [[[38856, 4975], 5, [1, 0, 2, 1, 0, 1]], [[9411393480, 1205005457],
 17, [1, 2, 1, 0, 5]], [[202546892400, 25933472143], 21, [5, 0, 2, 1]]]
?
\end{verbatim}
}
���Ϥ�, $y$ ������\ref{thm:set}�ν��� $S$ ��°����褦��
���٤Ƥβ�Υꥹ�ȤǤ���.
�Ʋ��3�Ĥ����Ǥǹ�������Ƥ���,
��� $(x,y)$, $n$, $(c_{n+1},\ldots,c_{n+m})$ �򼨤��Ƥ���.
���Ȥ���\texttt{[[202546892400, 25933472143], 21, [5, 0, 2, 1]]}��
\begin{alignat*}{2}
x &=& 202546892400
  &= 5 \cdot p_{21} + 0 \cdot p_{22} + 2 \cdot p_{23} + 1 \cdot p_{24}, \\
y &=& 25933472143
  &= 5 \cdot q_{21} + 0 \cdot q_{22} + 2 \cdot q_{23} + 1 \cdot q_{24}
\end{alignat*}
�Ǥ��뤳�Ȥ򼨤��Ƥ���.

\underline{\texttt{ac99(61,611,1)}}�����Ϥ����,
��Ĺ��ɽ�����ʤ����.
{\footnotesize
\begin{verbatim}
? ac99(61,611,1)
l: 11
a: [7, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14]
max and min of m: [13, 2]
p: [1, 7, 8, 39, 125, 164, 453, 1070, 1523, 5639, 24079, 29718, 440131,
469849, 2319527, 7428430, 9747957, 26924344, 63596645, 90520989, 3351596
12, 1431159437, 1766319049, 26159626123, 27925945172, 137863406811]
q: [0, 1, 1, 5, 16, 21, 58, 137, 195, 722, 3083, 3805, 56353, 60158, 296
985, 951113, 1248098, 3447309, 8142716, 11590025, 42912791, 183241189, 2
26153980, 3349396909, 3575550889, 17651600465]
n mod l, max and min of m wrt n: [0, 8, 1]
n mod l, max and min of m wrt n: [1, 7, 1]
n mod l, max and min of m wrt n: [2, 8, 1]
n mod l, max and min of m wrt n: [3, 8, 1]
n mod l, max and min of m wrt n: [4, 7, 1]
n mod l, max and min of m wrt n: [5, 8, 1]
solution: [[38856, 4975], 5, [1, 0, 2, 1, 0, 1]]
n mod l, max and min of m wrt n: [6, 7, 1]
solution: [[9411393480, 1205005457], 17, [1, 2, 1, 0, 5]]
n mod l, max and min of m wrt n: [7, 6, 1]
n mod l, max and min of m wrt n: [8, 6, 1]
n mod l, max and min of m wrt n: [9, 6, 1]
n mod l, max and min of m wrt n: [10, 6, 1]
solution: [[202546892400, 25933472143], 21, [5, 0, 2, 1]]
number of candidates: 916
%2 = [[[38856, 4975], 5, [1, 0, 2, 1, 0, 1]], [[9411393480, 1205005457],
 17, [1, 2, 1, 0, 5]], [[202546892400, 25933472143], 21, [5, 0, 2, 1]]]
?
\end{verbatim}
}
ɽ����������Ƥϼ����̤�.
���Ϥ�1���ܡ�\texttt{l:}�פ� $\sqrt{D}$ �ʺ��ξ��� $\sqrt{61}$�ˤ�
Ϣʬ��Ÿ���μ���,
2���ܤΡ�\texttt{a:}�פ���ʬ�� $a_0,a_1,\ldots,a_l$ �Ǥ���.
3���ܤ�ɽ����Ĺ�� $m$ �ξ�¤Ȳ��¤�
����\ref{thm:m1}�ˤ���᤿��ΤǤ���.
���Ρ�\texttt{p:}�פ� $p_{-1},p_0,p_1,\ldots$,
��\texttt{q:}�פ� $q_{-1},q_0,q_1,\ldots$ �Ǥ���.
���θ�� $0 \le n \le l-1$ �ʤ� $n$ ���줾��ˤĤ���,
����\ref{thm:m2}�ˤ�� $m$ �ξ�¤Ȳ��¤����Ƶ�᤿���,
���õ����ԤäƤ���.
������, $n=0$ �ξ��ˤ����Ƥ�,
����\ref{thm:m2}��Ŭ�Ѥ���Ȥ��Τ� $n=l$ �Ȥ��Ƥ���.
�� $n$ ���Ȥ�, ���Ĥ��ä�����༡ɽ������.
�Ǹ�Ρ�\texttt{number of candidates:}�פϽ��� $S$ �θ��θĿ��Ǥ���.


\begin{thebibliography}{9}
\bibitem{Hashimoto1}
{Hashimoto, Ry\=uta}.
  \newblock Note on a theorem of Rockett and Sz\"usz
  on a diophantine equation $x^2-Dy^2=N$.
  \newblock {\em submitted}.
\bibitem{Hashimoto2}
{Hashimoto, Ry\=uta}.
  \newblock On forms of integer solutions
  of a diophantine equation $x^2-Dy^2=N$.
  \newblock {\em in preparation}.
\bibitem{jssac99}
{���� ε��}.
  \newblock 2��2��������������������Ostrowskiɽ���ˤĤ���.
  \newblock ��8�����ܿ��������ز����ˤ�����ֱ�. 1999.
  \\
  \texttt{http://www.math.human.nagoya-u.ac.jp/\~{}ryuuta/distrib/}
\bibitem{RocSzu86}
{Rockett, Andrew M.} and {Sz\"usz, Peter}.
  \newblock A localization theorem
  in the theory of diophantine approximation
  and an application to Pell's equation,
  \newblock {\em Acta Arith.}, 47(4):347--350, 1986.
\bibitem{RocSzu}
{Rockett, Andrew M.} and {Sz\"usz, Peter}.
  \newblock {\em Continued Fractions}.
  \newblock World Scientific, Singapore, 1992.
\bibitem{Takagi}
�����缣.
  \newblock {�����������ֵ� ��2��}.
  \newblock ��Ω����, 1971.
\end{thebibliography}


\begin{flushright}
Ry\=uta Hashimoto \\
Graduate School of Human Informatics, Nagoya Univ. \\
e-mail: \texttt{ryuuta@math.human.nagoya-u.ac.jp}\\
URL: \texttt{http://www.math.human.nagoya-u.ac.jp/\~{}ryuuta/}
\end{flushright}

\end{document}
