# Solve Pell's equation

Bonjour, How can I solve a pell's equation $$x^2-181y^2=180$$? I try continued fraction method but it is too long.

• Factorise the ideal equation in $\mathbb{Z}[(1+\sqrt{181})/2]$ as usual. It is long because it is! The fundamental unit $m+n(1+\sqrt{181})/2$ with $m>10^{18}$. Commented Jun 20, 2019 at 10:44
• See Wikipedia, you need to use fundamental solution to find all solution , and you can find fundamental one using brahmcharya identity Commented Jun 20, 2019 at 10:45
• Sorry, what is Brahmcharya identity? Commented Jun 20, 2019 at 10:46
• @user10354138 Can you please clarify your answer of factorising the ideal equation by giving one or two iterations please? Commented Jun 20, 2019 at 10:48
• @WillJagy Well indeed, there is a programming contest between a few groups online.. You seem to have the nose of a bloodhound! :-D Commented Jun 20, 2019 at 18:05

Get all fundamental/root/seed solutions in pari/gp:

? bnfisintnorm(bnfinit('X^2-181),180)
%1 = [-604*X + 8126, X + 19, -12*X - 162, 12*X - 162, -X + 19, -701*X + 9431]


Get all (in some limits of power of fundamental unit) solutions of source equation and ordered set of $$X$$:

pell()=
{
SX= Set();
Q= bnfinit('X^2-181);
fu= Q.fu[1]; print("Fundamental Unit: "fu"\n");
N= bnfisintnorm(Q, 180);  print("Fundamental Solutions: "N"\n");
for(k=1, #N, n= N[k];
for(l=0, 10,
s= lift(n*fu^l);
X= abs(polcoeff(s, 0)); Y= abs(polcoeff(s, 1));
if(X^2-181*Y^2==180, print1("("X","Y"), "); SX= setunion(SX, [X]))
)
);
print("\n\nX= "SX)
};


Output:

? pell()
Fundamental Unit: Mod(97/2*X - 1305/2, X^2 - 181)

Fundamental Solutions: [-604*X + 8126, X + 19, -12*X - 162, 12*X - 162, -X + 19, -701*X
+ 9431]

(8126,604), (13838787971,1028629009), (23567829561880091,1751782975309639), (40136650075
266126947486,2983333705091619948244), (68353798767706678547434360031,5080697849779314462
622824949), (116408364853931064996526229733566351,8652565617013133237632070084472379), (
19,1), (4722814,351044), (8043079757959,597837410189), (13697581990952919079,10181332511
61591059), (23327351965298533840594174,1733908416325373099025404), (39727110235392768608
954621445619,2952892848528333039462775106849), (162,12), (473877,35223), (807025325517,5
9985720033), (1374385919038766082,102157300830604668), (2340616328542025659004697,173976
641561582190210003), (3986132804146565946058753351737,296286917948594475345940174413), (
162,12), (275416497,20471547), (469041730636257,34863597272757), (798790731399997433442,
59373647472611063892), (1360362182923474387351792677,101114924734303538709528327), (2316
733527296817024737161429899837,172201446925427378970399287081937), (19,1), (27634699,205
4071), (47062638533854,3498138372916), (80148944114366141359,5957424098809962661), (1364
95815848209563981659839,10145654090720536142301931), (232456059776448640174879844491294,
17278322849151565080717220682476), (9431,701), (16061239511,1193822531), (27352724540690
366,2033112003500636), (46582428416342230698371,3462444635984483802641), (79331133318570
707395013978651,5896636701084714384956793671), (135103061982078933674392128789378206,100
42131511134735440233828971339476),

X= [19, 162, 8126, 9431, 473877, 4722814, 27634699, 275416497, 13838787971, 16061239511,
807025325517, 8043079757959, 47062638533854, 469041730636257, 23567829561880091, 273527
24540690366, 1374385919038766082, 13697581990952919079, 80148944114366141359, 7987907313
99997433442, 40136650075266126947486, 46582428416342230698371, 2340616328542025659004697
, 23327351965298533840594174, 136495815848209563981659839, 1360362182923474387351792677,
68353798767706678547434360031, 79331133318570707395013978651, 3986132804146565946058753
351737, 39727110235392768608954621445619, 232456059776448640174879844491294, 23167335272
96817024737161429899837, 116408364853931064996526229733566351, 1351030619820789336743921
28789378206]


Verifing in Wolfram.

• How do you say that all non-fundamental solutions can be obtained from these four solutions? What is the proof? Commented Jun 23, 2019 at 9:43
• @silvestre_dubois Sorry, small incorrect in my answer. Fundamental solutions and fundamental unit given all solutions source equation. Need to multiply fundamental solution and power of fundamental unit. Fundamental unit of form X^2-181 is 97/2*X - 1305/2. I will added answer. Commented Jun 23, 2019 at 11:43