|
||
Title: Mirroring Continued Fractions Post by Barukh on Dec 22nd, 2008, 6:12am Let m, n, p be positive integers satisfying A. m, n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif p/2; mn = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1 mod p. 1. Prove: If simple continued fraction (SCF) of m/p is [0; a1, ..., an], then SCF of n/p is [0; an, ..., a1]. 2. What happens first condition is relaxed to: m, n < p? |
||
Title: Re: Mirroring Continued Fractions Post by Eigenray on Dec 22nd, 2008, 4:20pm Well, this is neat. Recall that in general, we have [ a0; a1, ..., an ] = pn/qn, where pk = ak pk-1 + pk-2; p-1 = 1, p0 = a0, qk = ak qk-1 + qk-2; q0=1; q1 = a1. For short write this as [ a0; a1, ..., an ] = X(0,n) = P(0,n)/Q(0,n). [hideb] First note that Q(0,n) = P(1,n). The major realization is that P(0,n) = v T(an) ... T(a0) vt, where v = (1,0) and T(a) is the matrix [ [ a 1 ], [ 1 0 ] ]. Taking the transpose of the above, we see that P(0,n) = P(n,0). So now we let x = [ 0; a1, ..., an ], x' = [ 0; an, ..., a1 ]. Then x = 1/X(1,n) = Q(1,n)/P(1,n) = qn/pn x' = 1/X(n,1) = Q(n,1)/P(n,1) = P(1,n-1)/P(1,n) = pn-1/pn, where pn/qn are the convergents to 1/x = [ a1 ; a2, ..., an ]. But it's another general fact that pn qn-1 - pn-1 qn = (-1)n-1. So the product of the two numerators, qnpn-1, is congruent to (-1)n mod pn, the denominator. We are almost done; the only issue now is uniqueness. Recall that any (non-one) fraction has two continued fraction expansions: one where the last term is 1, and another where the last term is > 1. If we start with the expansion of m/p where aN > 1, then the reversal with be a fraction q/p = [ 0; aN, aN-1, ... ] http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 1/2, while if take the one where aN = 1, then the reversal will be q'/p = [ 0; 1, ... ] http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 1/2. So if we start with any fraction m/p < 1, it will have two reversals, q/p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 1/2, and q'/p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 1/2, satisfying mq = -mq' = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif 1 mod p. But these two conditions uniquely determine q and q', so one of them must be the fraction n/p we were given, depending on whether n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif p/2 or n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif p/2. (Of course if p=2, there is only one possibility.)[/hideb] |
||
Title: Re: Mirroring Continued Fractions Post by Barukh on Dec 23rd, 2008, 10:45am Nicely done, Eigenray! ;) Can we say that SCF of n/p is symmetric iff n is a 2-nd or 4-th root of 1 mod p? |
||
Title: Re: Mirroring Continued Fractions Post by Eigenray on Dec 23rd, 2008, 11:38pm Sure: n2 = (-1)k-1 mod p iff n/p = [ 0; a1, ..., ak ] is symmetric, if we take ak > 1 for n/p < 1/2, and ak=1 for n/p > 1/2. Suppose p = 4m+1 is prime. If we always take ak > 1, then pairing n/p with its reversal n'/p gives an involution of [ 1, 2m ]. Since 1/p is symmetric, there must be another fixed point n/p in this interval, and then we can only have n2 = -1 mod p. So we can write n/p = [ 0; a1, ..., at, at, ..., a1 ]. In fact, if we let a/b = [ 0; at, ..., a1 ], then p = a2+b2. |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |