Author |
Topic: Mirroring Continued Fractions (Read 1187 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print