wu :: forums « wu :: forums - Mirroring Continued Fractions » Welcome, Guest. Please Login or Register. Apr 18th, 2024, 4:39pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Icarus, william wu, towr, SMQ, Eigenray, Grimbal)    Mirroring Continued Fractions « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Mirroring Continued Fractions  (Read 1186 times)
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Mirroring Continued Fractions   « on: Dec 22nd, 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; a1, ..., an], then SCF of n/p is [0; an, ..., a1].

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 22nd, 2008, 4:20pm » Quote Modify

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).

 hidden: 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, ... ] 1/2, while if take the one where aN = 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 22nd, 2008, 4:23pm by Eigenray » IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: Mirroring Continued Fractions   « Reply #2 on: Dec 23rd, 2008, 10:45am » Quote Modify

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?
 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: Mirroring Continued Fractions   « Reply #3 on: Dec 23rd, 2008, 11:38pm » Quote Modify

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.
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board