 mersenneforum.org Can I borrow some ECM of a friendly CPU?
 Register FAQ Search Today's Posts Mark Forums Read  2022-08-30, 12:35 #23 Dr Sardonicus   Feb 2017 Nowhere 2·3·17·61 Posts As to the numerators N and denominators D for sqrt(23), the only ones with obvious divisibility properties are the ones with N^2 - 23*D^2 = 1. If Mod(Fk*x + Lk, x^2 - 23) = Mod(5*x + 24, x^2 - 23)^k then N4k = Lk and D4k = Fk. The F and L sequences have divisibility properties similar to those of the Fibonacci and Lucas numbers, respectively. The SCF for sqrt(n^2 + 1) has partial quotients n, 2n, 2n, ... [period has length 1]. so the numerators and denominators are the solutions to N^2 - (n^2 + 1)*D^2 = ±1. We have Dk = Fk, Nk = Lk, where Mod(Fk*x + Lk, x^2 - (n^2 + 1)) = Mod(n + x, x^2 - (n^2 + 1))^k for non-negative integer k. With the single exception n = 2, Mod(n + x, x^2 - (n^2 + 1)) is the fundamental unit for Q(Mod(x, x^2 - (n^2 + 1)) [i.e. Q(sqrt(n^2 + 1))]. So with the single exception n = 2, the numerators and denominators will have divisibility properties similar to those of the Lucas and Fibonacci numbers. With the SCF for sqrt(n^2 + 4), however, we see something similar to what happens with sqrt(5). [Note that 5 is the only positive integer which is simultaneously of the forms n^2 + 1 and n^2 + 4.] For n > 2, the sequence of partial quotients n, ... 2n will have period d > 1. Every d-th numerator N and denominator D will satisfy N2 - (n^2 + 4)*D2 = ±1. But in this case, the fundamental unit is Mod((x+n)/2, x^2 - (n^2 + 4)), and we have Mod(Ddk*x + Ndk , x^2 - (n^2 + 4)) = Mod((F3k*x + L3k)/2, x^2 - (n^2 + 4)) similar to the case n = 2. I was unable to discern any divisibility properties of the numerators N and denominators D for which |N2 - (n^2 + 4)*D2| > 1. Last fiddled with by Dr Sardonicus on 2022-08-30 at 23:13 Reason: xinfig topsy   2022-09-01, 14:43   #24
fatphil

May 2003

3×5×17 Posts Quote:
 Originally Posted by Dr Sardonicus As to the numerators N and denominators D for sqrt(23), the only ones with obvious divisibility properties are the ones with N^2 - 23*D^2 = 1. If Mod(Fk*x + Lk, x^2 - 23) = Mod(5*x + 24, x^2 - 23)^k then N4k = Lk and D4k = Fk. The F and L sequences have divisibility properties similar to those of the Fibonacci and Lucas numbers, respectively.
Thanks for this, I'm a bit rusty, and it will take several re-reads to sink in. I wish I had the mastery of Pari/GP I used to, so I could play around with these 2-dimensional objects - I'd completely forgotten the Mod(..., x^2-d) trick despite it being my go-to tool a decade back!
The 23 was incidentally completely arbitrary, which is why I immediately put it to one side and looked at smaller discriminants instead.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post hansl Math 3 2020-09-02 10:40 Sutton Shin mersennewiki 0 2012-09-29 08:03 davieddy Soap Box 9 2012-07-13 05:39 davieddy Lounge 1 2011-06-10 18:42 Xyzzy Lounge 11 2003-05-15 08:38

All times are UTC. The time now is 15:04.

Thu Feb 2 15:04:34 UTC 2023 up 168 days, 12:33, 1 user, load averages: 1.15, 0.90, 0.94