wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> putnam exam (pure math) >> Mirroring Continued Fractions
(Message started by: Barukh on Dec 22nd, 2008, 6:12am)

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