Author 
Topic: Mirroring Continued Fractions (Read 1186 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


Mirroring Continued Fractions
« on: Dec 22^{nd}, 2008, 6:12am » 
Quote Modify

Let m, n, p be positive integers satisfying A. m, n p/2; mn = 1 mod p. 1. Prove: If simple continued fraction (SCF) of m/p is [0; a_{1}, ..., a_{n}], then SCF of n/p is [0; a_{n}, ..., a_{1}]. 2. What happens first condition is relaxed to: m, n < p?


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Mirroring Continued Fractions
« Reply #1 on: Dec 22^{nd}, 2008, 4:20pm » 
Quote Modify

Well, this is neat. Recall that in general, we have [ a_{0}; a_{1}, ..., a_{n} ] = p_{n}/q_{n}, where p_{k} = a_{k} p_{k1} + p_{k2}; p_{1} = 1, p_{0} = a_{0}, q_{k} = a_{k} q_{k1} + q_{k2}; q_{0}=1; q_{1} = a_{1}. For short write this as [ a_{0}; a_{1}, ..., a_{n} ] = X(0,n) = P(0,n)/Q(0,n). hidden:  First note that Q(0,n) = P(1,n). The major realization is that P(0,n) = v T(a_{n}) ... T(a_{0}) v^{t}, 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; a_{1}, ..., a_{n} ], x' = [ 0; a_{n}, ..., a_{1} ]. Then x = 1/X(1,n) = Q(1,n)/P(1,n) = q_{n}/p_{n} x' = 1/X(n,1) = Q(n,1)/P(n,1) = P(1,n1)/P(1,n) = p_{n1}/p_{n}, where p_{n}/q_{n} are the convergents to 1/x = [ a_{1} ; a_{2}, ..., a_{n} ]. But it's another general fact that p_{n} q_{n1}  p_{n1} q_{n} = (1)^{n1}. So the product of the two numerators, q_{n}p_{n1}, is congruent to (1)^{n} mod p_{n}, the denominator. We are almost done; the only issue now is uniqueness. Recall that any (nonone) 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 a_{N} > 1, then the reversal with be a fraction q/p = [ 0; a_{N}, a_{N1}, ... ] 1/2, while if take the one where a_{N} = 1, then the reversal will be q'/p = [ 0; 1, ... ] 1/2. So if we start with any fraction m/p < 1, it will have two reversals, q/p 1/2, and q'/p 1/2, satisfying mq = mq' = 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 p/2 or n p/2. (Of course if p=2, there is only one possibility.) 

« Last Edit: Dec 22^{nd}, 2008, 4:23pm by Eigenray » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Mirroring Continued Fractions
« Reply #2 on: Dec 23^{rd}, 2008, 10:45am » 
Quote Modify

Nicely done, Eigenray! Can we say that SCF of n/p is symmetric iff n is a 2nd or 4th root of 1 mod p?


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Mirroring Continued Fractions
« Reply #3 on: Dec 23^{rd}, 2008, 11:38pm » 
Quote Modify

Sure: n^{2} = (1)^{k1} mod p iff n/p = [ 0; a_{1}, ..., a_{k} ] is symmetric, if we take a_{k} > 1 for n/p < 1/2, and a_{k}=1 for n/p > 1/2. Suppose p = 4m+1 is prime. If we always take a_{k} > 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 n^{2} = 1 mod p. So we can write n/p = [ 0; a_{1}, ..., a_{t}, a_{t}, ..., a_{1} ]. In fact, if we let a/b = [ 0; a_{t}, ..., a_{1} ], then p = a^{2}+b^{2}.


IP Logged 



