wu :: forums
wu :: forums - Mirroring Continued Fractions

Welcome, Guest. Please Login or Register.
Jun 8th, 2023, 11:29am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, Grimbal, Eigenray, william wu, SMQ, towr)
   Mirroring Continued Fractions
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Mirroring Continued Fractions  (Read 1167 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Mirroring Continued Fractions  
« on: Dec 22nd, 2008, 6:12am »
Quote Quote Modify 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: male
Posts: 1948
Re: Mirroring Continued Fractions  
« Reply #1 on: Dec 22nd, 2008, 4:20pm »
Quote Quote Modify 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: male
Posts: 2276
Re: Mirroring Continued Fractions  
« Reply #2 on: Dec 23rd, 2008, 10:45am »
Quote Quote Modify Modify

Nicely done, Eigenray!  Wink
 
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: male
Posts: 1948
Re: Mirroring Continued Fractions  
« Reply #3 on: Dec 23rd, 2008, 11:38pm »
Quote Quote Modify 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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