Ask Your Question
0

Generating the non-fundamental solutions of Pell's equation

asked 2023-01-30 12:26:29 +0200

anonymous user

Anonymous

updated 2023-01-30 13:36:56 +0200

Hi. The topic of Pell's equation seems to be quite minor among coding sites so I've come to ask for help from professionals at here SageMath community.

https://mathsci.kaist.ac.kr/cms/wp-co...

def solve_pell (N , numTry = 100):
    cf = continued_fraction ( sqrt ( N ))
    for i in range ( numTry ):
        denom = cf.denominator ( i )
        numer = cf.numerator ( i )
        if numer ^2 - N * denom ^2 == 1:
            return numer , denom
    return None , None


solve_pell (21)

The code attached in the last page of the link above works really fine. It finds the fundamental solutions of Pell's equation and I've never seen any other shorter code than the code in the link.

I usually prefer to use the library codes than my self-made codes for the sake of efficiency. However if there aren't any relevant sources, I would have no other choices but make some new codes.

So my questions,

1. Are there any library functions, the libraries that are supported by Sage, regarding finding the non-fundamental solutions of Pell's equation?

2. If not, could you suggest some idea for the code which do the task we desire?

I've tried to make my own code by referring to the algorithm in a document from Wikipedia

however it seems to be using symbolic computations heavily of which I've never tried before. I would be glad for any kind of advice via commens and answers. Thanks.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
2

answered 2023-01-30 16:24:52 +0200

achrzesz gravatar image

updated 2023-01-30 16:30:52 +0200

Look https://wstein.org/books/ant/ant.pdf, page 93

K.< sqrt21 > = QuadraticField (21)
G = K.unit_group ()
u0,u1=G.gens()
u=K(u1);u

-1/2*sqrt21 + 5/2

[ list (u^i ) for i in range(3,20,3)]

[[55, -12],
 [6049, -1320],
 [665335, -145188],
 [73180801, -15969360],
 [8049222775, -1756484412],
 [885341324449, -193197315960]]
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2023-01-30 12:26:29 +0200

Seen: 180 times

Last updated: Jan 30 '23