-

必要に応じて、x^2-d'(ny)^2=cと置き換えることにより、dは平方因子を持たないとしてよい。
dが1のとき、左辺を因数分解すると自明。以下dは平方因子を持たない1でない正整数とする。

■c=1の場合
√dの連分数展開により解を得られる。
これはQ(√d)の基本単数を求めていることと同値

以下、(x,y)とx+y√dを暗黙的に同一視する。

■一般の場合
x^2-dy^2=1の正整数の解であって最小のものを取り、Z=X+Y√dとおく。ZとZ^-1=X-Y√dはZ[√d]の元である。
Z[√d]はQ(√d)の整数環の部分環だから、ノルムが定義され、問いは「N(z)=cとなるzを求めよ」と読み替えられる。
Zは「Z＞1かつN(Z)=1」を満たす最小の元である。
N(z)=cの解zを任意に取ったとき、zZもまた解になる。全ての解は、いくつかの初期解ziを用いてzi*Z^nの形で表される。

手続き的に全ての解法を求める方法や、範囲を狭めて全探索をする方法などがある

・全探索解法
Z＞1であることから、任意のzに対してある整数nが存在して、√(|c|/Z)≦|zZ^n|＜√(|c|Z) となる。
したがって、N(z)=cを満たすzに対してnをそのようにとると、zZ^n=:z'=x'+y'√dに対して、z'z'~=cであることから
2|x'|=|z'+c/z'|≦max|t+|c|/t|≦(Z+1)/(2√Z)*√|c| を得る。
（maxはt∈[√(|c|/Z),√(|c|Z))の範囲を動くが、関数は下に凸なので、最大値は両端のどっちかであり直接計算する）
この範囲を全探索すればよい。
この証明は以下に基づく（もとの証明には誤りが含まれる）
https://imomath.com/index.cgi?page=ntPellsEquationPellType

・素因数分解解法
d=-1のとき、Z[√-1]でcを素因数分解する問題になったのと同様に、Z[√d]でcを素因数分解する問題である……？
これは、Q(√d)の類数が1の場合なら正しい（整数環がUFDなので）
このときは、有理素数pがQ(√d)でどうなるかを調べればよい。
DをQ(√d)の判別式とする。すなわちd=1 mod 4 のときD=d、そうでないときD=4dとする。このとき、クロネッカー記号(D|p)が1,-1,0のいずれであるかにより、pはZ[√d]で分解・惰性・分岐する。
https://en.wikipedia.org/wiki/Kronecker_symbol
https://www.rs.tus.ac.jp/a25594/2013_Number_Theory.pdf
P21定理41

・手続き的解法
(x,y)が互いに素でない解が存在するなら、(px)^2-d(py)^2=c/p^2となるので、cを取り替えながら、(x,y)が互いに素な解を全て求める事ができれば十分。
√dの連分数近似をp1/q1,p2/q2,…とする。
|c|＜√dであるとき、N(z)=cの解は(pi,qi)の形のものに限る。
0以上c/2以下の整数Kであって、c':=(K^2-d)/cが絶対値c未満の整数となるようなものを全て取る（とれないとき、解は存在しない）
このとき、x'^2-dy'^2=c'の解(a,b)から、もとの方程式の解は
bx-ay=±1
ax-dby=K
を解くことで得られる。具体的には(x,y)=(aK±bD,bk±a) (複号同順)である。
(これは線形方程式なのでa＞0の分だけ考えて解を得て、最後に±(x,y)を解とすると手抜きができる)
|c'|＜|c|であったことから、これを繰り返すことで、|c|＜√dのケースに帰着できる
http://djm.cc/library/Algebra_Elementary_Text-Book_Part_II_Chrystal_edited02.pdf
P479セクション16～18（PE137のthreadより）
https://web.archive.org/web/20180831180333/http://www.jpr2718.org/pell.pdf
未読（PE140のthreadより）