Explanation of functions:

dnorm(x,d) : calculates the norm of  for the modulus d.

bhav(x,y,d): calculates the bhavana (product in our field) of x,y with modulus d.

mbh(list,d): multi-bhavana on a list.

res( ) solves .

nres( ,d) solves as above and reports an answer an optimal answer - the one with smallest norm with modulus d.

The answer is a triple [a,1,c] where c is the dnorm of (a,1).

improve(u,d) uses the nres and combines u with the optimal solution. d is the modulus.

imp(u,d) same as improve, except it skips the multiplication (bhavana). Answer is a new triple with the leftover part of the dnorm at the end.

red(u,a,d) factors out a from u and reports a triple  where c is the new dnorm.

dolist(list,d) keeps on extending the list by improving and reducing the last created (actually the first) term!

dolis is the same, except uses imp and hence leaves the parts unmultiplied.

build(list,d) Finishes the multiplications postponed in dolis.

>

Functions

>	dnorm:=(x,d)->x[1]^2-d*x[2]^2:# norm w.r.t. d

>	bhav:=proc(x,y,d) local ans,tmpx,tmpy,var,tmp; #Bhavana of Brahmagupta-Bhaskara tmpx:=x[1]+var*x[2];tmpy:=y[1]+var*y[2]; tmp:=expand(tmpx*tmpy);tmp:=subs(var^2=d,tmp); ans:=[coeff(tmp,var,0),coeff(tmp,var,1)]; ans:=[op(ans),dnorm(ans,d)];end:

>	mbh:=proc(lis,d) local ans,i;#multiple bhavana ans:=lis[1]; for i from 2 to nops(lis) do; ans:=bhav(ans,lis[i],MD); od; ans; end:

>	res:=proc(u) local ans,x;#resolution for a suitable unitary sol. ans:=msolve(u[1]+u[2]*x,abs(u[3])); end:

>

nres:=proc(u,d) local tmp,ans,x,a1,a2;# Same as res, except the answer is a triple. tmp:=msolve(u[1]+u[2]*x,abs(u[3])); ans:=subs(tmp,x);while ans^2<d do;  #print(ans); ans:=ans+abs(u[3]); od; a2:=abs(ans^2-d);a1:=abs((ans-abs(u[3]))^2-d);  #print(ans,a1,a2); if a1<=a2 then ans:=ans-abs(u[3]);fi; #print([ans,1,dnorm([ans,1],d)]); [ans,1,dnorm([ans,1],d)]; end:

>	improve:=(u,d)->bhav(u,nres(u,d),d): #combines u with its resolution. imp:=proc(u,d) local tmp,ans; tmp:=nres(u,d); print(tmp[3],u[3]);ans:=[tmp[1],tmp[2],tmp[3]/u[3]]:end:

>	red:=proc(u,a,d) local ans;   #Factors out a from u ans:=[u[1]/a,u[2]/a]; ans:=[op(ans),dnorm(ans,d)];end:

>

dolist:=proc(l,d) local lis,tmp; # shortcut to improvement in a list! lis:=l; #nres(lis[1],d); tmp:=improve(lis[1],d); tmp:=red(tmp,abs(lis[1][3]),d);lis:=[%,op(lis)]; end: ## dolis:=proc(l,d) local lis,tmp; # shortcut to improvement in a list! lis:=l; #nres(lis[1],d); tmp:=imp(lis[1],d); lis:=[tmp,op(lis)]; end: ## build:=proc(lis,MD) local tmp,ans,i,n; n:=nops(lis); tmp:=[seq([lis[i][1],lis[i][2]],i=1..n)]:print(tmp): tmp:=mbh(tmp,MD); ans:=red(tmp,product(lis[i][3],i=1..n),MD);end:

>

;

>	dolis([[10,1,-3]],103);

$18,-3$

$\left[\left[11,1,-6\right],\left[10,1,-3\right]\right]$

>	dolist(%,103);

$\left[\left[30,3,-27\right],\left[11,1,-6\right],\left[10,1,-3\right]\right]$

The above is now exclusively used in the worksheet!

>	red([27,6,45],3,19);

$\left[9,2,5\right]$

>	nres([4,1,-3],19);

$\left[5,1,6\right]$

Case of 11

>	MD:=11;l11:=[[3,1,dnorm([3,1],11)]];

$\mathrm{MD}:=11$

$\mathrm{l11}:=\left[\left[3,1,-2\right]\right]$

>	dolis(l11,MD);

$-2,-2$

$\left[\left[3,1,1\right],\left[3,1,-2\right]\right]$

>	build(%,MD);

$\left[\left[3,1\right],\left[3,1\right]\right]$

$\left[-10,-3,1\right]$

>

>

Case of  17

>

MD:=17;

$\mathrm{MD}:=17$

>	l17:=[[4,1,dnorm([4,1],MD)]];

$\mathrm{l17}:=\left[\left[4,1,-1\right]\right]$

Case of 19

>	MD:=19; #modulus is set to 19

$\mathrm{MD}:=19$

>	l19:=[[4,1,dnorm([4,1],MD)]];

$\mathrm{l19}:=\left[\left[4,1,-3\right]\right]$

>	dolis(l19,MD);

$6,-3$

$\left[\left[5,1,-2\right],\left[4,1,-3\right]\right]$

>	dolis(%,MD);

$6,-2$

$\left[\left[5,1,-3\right],\left[5,1,-2\right],\left[4,1,-3\right]\right]$

>	dolis(%,MD);

$-3,-3$

$\left[\left[4,1,1\right],\left[5,1,-3\right],\left[5,1,-2\right],\left[4,1,-3\right]\right]$

>	build(%,MD);

$\left[\left[4,1\right],\left[5,1\right],\left[5,1\right],\left[4,1\right]\right]$

$\left[-170,-39,1\right]$

>

Case of 43

>

MD:=43;

$\mathrm{MD}:=43$

>	l43:=[[7,1,dnorm([7,1],MD)]];

$\mathrm{l43}:=\left[\left[7,1,6\right]\right]$

>	dolist(%,MD);

$\left[\left[13,2,-3\right],\left[7,1,6\right]\right]$

>	dolist(%,MD);

$\left[\left[59,9,-2\right],\left[13,2,-3\right],\left[7,1,6\right]\right]$

>	dolist(%,MD);

$\left[\left[400,61,-3\right],\left[59,9,-2\right],\left[13,2,-3\right],\left[7,1,6\right]\right]$

>	dolist(%,MD);

$\left[\left[1541,235,6\right],\left[400,61,-3\right],\left[59,9,-2\right],\left[13,2,-3\right],\left[7,1,6\right]\right]$

>	dolist(%,MD);

$\left[\left[3482,531,1\right],\left[1541,235,6\right],\left[400,61,-3\right],\left[59,9,-2\right],\left[13,2,-3\right],\left[7,1,6\right]\right]$

>	bhav([59,9],[7,1],MD);red(%,2,MD);

$\left[800,122,-12\right]$

$\left[400,61,-3\right]$

>	bhav([400,61],[5,1],MD);red(%,3,MD);

$\left[4623,705,54\right]$

$\left[1541,235,6\right]$

>	bhav([1541,235],[7,1],MD);red(%,6,MD);

$\left[20892,3186,36\right]$

$\left[3482,531,1\right]$

>	dnorm([3482,531],MD);

$1$

>

>	dolis(l43,MD);

$-18,6$

$\left[\left[5,1,-3\right],\left[7,1,6\right]\right]$

>	dolis(%,MD);

$6,-3$

$\left[\left[7,1,-2\right],\left[5,1,-3\right],\left[7,1,6\right]\right]$

>	dolis(%,MD);

$6,-2$

$\left[\left[7,1,-3\right],\left[7,1,-2\right],\left[5,1,-3\right],\left[7,1,6\right]\right]$

>	dolis(%,MD);

$-18,-3$

$\left[\left[5,1,6\right],\left[7,1,-3\right],\left[7,1,-2\right],\left[5,1,-3\right],\left[7,1,6\right]\right]$

>	dolis(%,MD);

$6,6$

$\left[\left[7,1,1\right],\left[5,1,6\right],\left[7,1,-3\right],\left[7,1,-2\right],\left[5,1,-3\right],\left[7,1,6\right]\right]$

>

Case of 47

>	MD:=47: #Modulus is 47;

>	lis47:=[[7,1,dnorm([7,1],MD)]];

$\mathrm{lis47}:=\left[\left[7,1,2\right]\right]$

>	dolis(%,MD);

$2,2$

$\left[\left[7,1,1\right],\left[7,1,2\right]\right]$

>	build(%,MD);

$\left[\left[7,1\right],\left[7,1\right]\right]$

$\left[48,7,1\right]$

>

>

Case of 57

>	MD:=57:# Modulus=57

>	lis57:=[[8,1,dnorm([8,1],MD)]];

$\mathrm{lis57}:=\left[\left[8,1,7\right]\right]$

>	dolis(%,MD);

$-21,7$

$\left[\left[6,1,-3\right],\left[8,1,7\right]\right]$

>	dolis(%,MD);

$-21,-3$

$\left[\left[6,1,7\right],\left[6,1,-3\right],\left[8,1,7\right]\right]$

>	dolis(%,MD);

$7,7$

$\left[\left[8,1,1\right],\left[6,1,7\right],\left[6,1,-3\right],\left[8,1,7\right]\right]$

>	build(%,MD);

$\left[\left[8,1\right],\left[6,1\right],\left[6,1\right],\left[8,1\right]\right]$

$\left[-151,-20,1\right]$

>

>

>

Case of 58

>	MD:=58; #modulus is set to 58

>	u1:=[8,1];dnorm(u1,MD);

$\mathrm{MD}:=58$

$\mathrm{u1}:=\left[8,1\right]$

$6$

>	l58:=[[op(u1),dnorm(u1,MD)]];

$\mathrm{l58}:=\left[\left[8,1,6\right]\right]$

>	dolis(l58,MD);

$-42,6$

$\left[\left[4,1,-7\right],\left[8,1,6\right]\right]$

>	dolis(%,MD);

$42,-7$

$\left[\left[10,1,-6\right],\left[4,1,-7\right],\left[8,1,6\right]\right]$

>	dolis(%,MD);

$6,-6$

$\left[\left[8,1,-1\right],\left[10,1,-6\right],\left[4,1,-7\right],\left[8,1,6\right]\right]$

>	build(%,MD);

$\left[\left[8,1\right],\left[10,1\right],\left[4,1\right],\left[8,1\right]\right]$

$\left[-99,-13,-1\right]$

>	bhav([99,13],[99,13],MD);

$\left[19603,2574,1\right]$

Case of  67

>

>

MD:=67;

$\mathrm{MD}:=67$

Case of 61

>

MD:=61;

$\mathrm{MD}:=61$

>	l61:=[[8,1,dnorm([8,1],MD)]];

$\mathrm{l61}:=\left[\left[8,1,3\right]\right]$

>	dolis(%,MD);

$-12,3$

$\left[\left[7,1,-4\right],\left[8,1,3\right]\right]$

>	dolis(%,MD);

$20,-4$

$\left[\left[9,1,-5\right],\left[7,1,-4\right],\left[8,1,3\right]\right]$

>	dolis(%,MD);

$-25,-5$

$\left[\left[6,1,5\right],\left[9,1,-5\right],\left[7,1,-4\right],\left[8,1,3\right]\right]$

>	dolis(%,MD);

$20,5$

$\left[\left[9,1,4\right],\left[6,1,5\right],\left[9,1,-5\right],\left[7,1,-4\right],\left[8,1,3\right]\right]$

>	dolis(%,MD);

$-12,4$

$\left[\left[7,1,-3\right],\left[9,1,4\right],\left[6,1,5\right],\left[9,1,-5\right],\left[7,1,-4\right],\left[8,1,3\right]\right]$

>	dolis(%,MD);

$3,-3$

$\left[\left[8,1,-1\right],\left[7,1,-3\right],\left[9,1,4\right],\left[6,1,5\right],\left[9,1,-5\right],\left[7,1,-4\right],\left[8,1,3\right]\right]$

>	build(%,MD);

$\left[\left[8,1\right],\left[7,1\right],\left[9,1\right],\left[6,1\right],\left[9,1\right],\left[7,1\right],\left[8,1\right]\right]$

$\left[29718,3805,-1\right]$

>

>

>

Shortcut!

>	bhav([39,5],[39^2+2,39*5],MD);

$\left[118872,15220,-16\right]$

>	red(%,4,MD);

$\left[29718,3805,-1\right]$

Case of 92

>

MD:=92;

$\mathrm{MD}:=92$

>	l92:=[[9,1,dnorm([9,1],MD)]];

$\mathrm{l92}:=\left[\left[9,1,-11\right]\right]$

Alternate treatment using 4.

>	bhav([48,5],[48,5],92);

$\left[4604,480,16\right]$

>	red(%,4,92);

$\left[1151,120,1\right]$

Case of 88

>

MD:=88;

$\mathrm{MD}:=88$

>	l88:=[[9,1,dnorm([9,1],MD)]];

$\mathrm{l88}:=\left[\left[9,1,-7\right]\right]$

>	dolis(%,MD);

$56,-7$

$\left[\left[12,1,-8\right],\left[9,1,-7\right]\right]$

>	dolis(%,MD);

$56,-8$

$\left[\left[12,1,-7\right],\left[12,1,-8\right],\left[9,1,-7\right]\right]$

>	dolis(%,MD);

$-7,-7$

$\left[\left[9,1,1\right],\left[12,1,-7\right],\left[12,1,-8\right],\left[9,1,-7\right]\right]$

>	build(%,MD);

$\left[\left[9,1\right],\left[12,1\right],\left[12,1\right],\left[9,1\right]\right]$

$\left[-197,-21,1\right]$

Case of 97

>

MD:=97;

$\mathrm{MD}:=97$

>	l97:=[[10,1,dnorm([10,1],MD)]];

$\mathrm{l97}:=\left[\left[10,1,3\right]\right]$

>	dolis(%,MD);

$24,3$

$\left[\left[11,1,8\right],\left[10,1,3\right]\right]$

>	dolis(%,MD);

$-72,8$

$\left[\left[5,1,-9\right],\left[11,1,8\right],\left[10,1,3\right]\right]$

>	dolis(%,MD);

$72,-9$

$\left[\left[13,1,-8\right],\left[5,1,-9\right],\left[11,1,8\right],\left[10,1,3\right]\right]$

>	dolis(%,MD);

$24,-8$

$\left[\left[11,1,-3\right],\left[13,1,-8\right],\left[5,1,-9\right],\left[11,1,8\right],\left[10,1,3\right]\right]$

>	dolis(%,MD);

$3,-3$

$\left[\left[10,1,-1\right],\left[11,1,-3\right],\left[13,1,-8\right],\left[5,1,-9\right],\left[11,1,8\right],\left[10,1,3\right]\right]$

>	build(%,MD);

$\left[\left[10,1\right],\left[11,1\right],\left[13,1\right],\left[5,1\right],\left[11,1\right],\left[10,1\right]\right]$

$\left[5604,569,-1\right]$

Case of 103

>

MD:=103;

$\mathrm{MD}:=103$

>	dnorm([477,47],MD);

$2$

>	bhav([477,47],[477,47],MD);

$\left[455056,44838,4\right]$

>	red(%,2,MD);

$\left[227528,22419,1\right]$

Case of 107

>

MD:=107;

$\mathrm{MD}:=107$

>	l107:=[[10,1,dnorm([10,1],MD)]];

$\mathrm{l107}:=\left[\left[10,1,-7\right]\right]$

>	dolis(%,MD);

$14,-7$

$\left[\left[11,1,-2\right],\left[10,1,-7\right]\right]$

>	dolis(%,MD);

$14,-2$

$\left[\left[11,1,-7\right],\left[11,1,-2\right],\left[10,1,-7\right]\right]$

>	dolis(%,MD);

$-7,-7$

$\left[\left[10,1,1\right],\left[11,1,-7\right],\left[11,1,-2\right],\left[10,1,-7\right]\right]$

>	build(%,MD);

$\left[\left[10,1\right],\left[11,1\right],\left[11,1\right],\left[10,1\right]\right]$

$\left[-962,-93,1\right]$

>	bhav([31,3],[31,3],MD);

$\left[1924,186,4\right]$

>	red(%,2,MD);

$\left[962,93,1\right]$

Case of 433

>

MD:=433;

$\mathrm{MD}:=433$

>	l433:=[[21,1,dnorm([21,1],MD)]];

$\mathrm{l433}:=\left[\left[21,1,8\right]\right]$

>	dolis(%,MD);

$-72,8$

$\left[\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$-144,-9$

$\left[\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$-208,16$

$\left[\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$143,-13$

$\left[\left[24,1,-11\right],\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$-33,-11$

$\left[\left[20,1,3\right],\left[24,1,-11\right],\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$51,3$

$\left[\left[22,1,17\right],\left[20,1,3\right],\left[24,1,-11\right],\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$-289,17$

$\left[\left[12,1,-17\right],\left[22,1,17\right],\left[20,1,3\right],\left[24,1,-11\right],\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$51,-17$

$\left[\left[22,1,-3\right],\left[12,1,-17\right],\left[22,1,17\right],\left[20,1,3\right],\left[24,1,-11\right],\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$-33,-3$

$\left[\left[20,1,11\right],\left[22,1,-3\right],\left[12,1,-17\right],\left[22,1,17\right],\left[20,1,3\right],\left[24,1,-11\right],\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$143,11$

$\left[\left[24,1,13\right],\left[20,1,11\right],\left[22,1,-3\right],\left[12,1,-17\right],\left[22,1,17\right],\left[20,1,3\right],\left[24,1,-11\right],\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$-208,13$

$\left[\left[15,1,-16\right],\left[24,1,13\right],\left[20,1,11\right],\left[22,1,-3\right],\left[12,1,-17\right],\left[22,1,17\right],\left[20,1,3\right],\left[24,1,-11\right],\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$-144,-16$

$\left[\left[17,1,9\right],\left[15,1,-16\right],\left[24,1,13\right],\left[20,1,11\right],\left[22,1,-3\right],\left[12,1,-17\right],\left[22,1,17\right],\left[20,1,3\right],\left[24,1,-11\right],\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$-72,9$

$\left[\left[19,1,-8\right],\left[17,1,9\right],\left[15,1,-16\right],\left[24,1,13\right],\left[20,1,11\right],\left[22,1,-3\right],\left[12,1,-17\right],\left[22,1,17\right],\left[20,1,3\right],\left[24,1,-11\right],\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	dolis(%,MD);

$8,-8$

$\left[\left[21,1,-1\right],\left[19,1,-8\right],\left[17,1,9\right],\left[15,1,-16\right],\left[24,1,13\right],\left[20,1,11\right],\left[22,1,-3\right],\left[12,1,-17\right],\left[22,1,17\right],\left[20,1,3\right],\left[24,1,-11\right],\left[15,1,-13\right],\left[17,1,16\right],\left[19,1,-9\right],\left[21,1,8\right]\right]$

>	build(%,MD);

$\left[\left[21,1\right],\left[19,1\right],\left[17,1\right],\left[15,1\right],\left[24,1\right],\left[20,1\right],\left[22,1\right],\left[12,1\right],\left[22,1\right],\left[20,1\right],\left[24,1\right],\left[15,1\right],\left[17,1\right],\left[19,1\right],\left[21,1\right]\right]$

$\left[7230660684,347483377,-1\right]$

>	with(numtheory):

>	cfrac(sqrt(403),'periodic');;

$20+\frac{1}{13+\frac{1}{2+\frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{2+\frac{1}{13+\frac{1}{40+\frac{1}{13+\frac{1}{2+\frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{2+\frac{1}{13+\frac{1}{40+\mathrm{...}}}}}}}}}}}}}}}}}}}}}$

>

periodic;

$\mathrm{periodic}$

>

?cfrac

>