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.

 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