[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1354.0. "theorem about divisibility and quadratic surds (needed for continued fraction work)" by HANNAH::OSMAN (see HANNAH::IGLOO$:[OSMAN]ERIC.VT240) Wed Dec 12 1990 17:27

T.RTitleUserPersonal
Name
DateLines
1354.1proof of correctness of Osman's algorithmGUESS::DERAMOSometimes they leave skid marks.Thu Dec 13 1990 00:5649
        Okay, here goes.  We start with
        
        	(sqrt(a) + b)/c
        
        where a,b,c are integers, a and c positive, and let n be
        the greatest integer <= (sqrt(a) + b)/c
        
        Further, let us assume that
        
        	c | (a - b^2)
        
        So (sqrt(a) + b)/c = n + ((sqrt(a) + b)/c - n)
        	= n + (sqrt(a) + (b-cn))/c
        	= n + 1 / c/(sqrt(a) + (b-cn))
        	= n + 1 / (c (sqrt(a) - (b-cn)))/(a - (b-cn)^2)
        	= n + 1 / (sqrt(a) + (cn-b))/( (a - (b-cn)^2)/c )
        	= n + 1 / (sqrt(a) + B)/C
        
        where
        
        	B = cn-b	C = (a - (b-cn)^2)/c
        
        The goal is that C be an integer, i.e., c | a-(b-cn)^2
        
        Well, a-(b-cn)^2 = a - b^2 + 2bcn - c^2n^2
        	= a - b^2 + c(2bn - cn^2)
        
        Since I fortunately assumed that c | a-b^2, it therefore
        follows that c | a-(b-cn)^2, i.e. that C is an integer.
        
        Now what makes this go on, is that you can now show that
        
        	C | a - B^2
        
        This is because a - B^2 = a - (cn-b)^2 = cC.
        
        So if you start with a=any positive integer, b=0 and c=1,
        then c | a-b^2 is satisfied and you get
        
        	sqrt(a) = n + 1 / (sqrt(a) + B)/C
        
        where again a,B,C are integers, a and C positive, and
        C | a-B^2 ... so you can continue this process until some
        triple a,b',c' along the way is repeated.
        
        Finally, if c fails to divide a-b^2, then c will fail to
        divide a-(b-cn)^2.
        
        Dan
1354.2please explain that last sentence: "Finally, if c fails to divide..."HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Thu Dec 13 1990 11:516
What does that sentence mean ?  That only surds arrived at starting with
a pure surd of the form sqrt(a) can be continued from, and that other starting
points will run amuk ?

/Eric
1354.3oopsGUESS::DERAMOSometimes they leave skid marks.Thu Dec 13 1990 11:5623
        In .1 I don't believe I ever used the assumption c > 0 (I
        did use c != 0), but that's okay as I didn't show that it
        was preserved in the next step. :-)
        
        So let us assume c > 0.  Then C = (a - (b-cn)^2)/c has a
        positive denominator.  Is the numerator positive?  Well,
        
        	n <= (sqrt(a) + b)/c < n+1
        
        so
        
        	cn <= sqrt(a) + b < cn + 1
                cn-b <= sqrt(a) < (cn-b) + 1
        
        Not knowing the sign of cn-b I don't see how to go any
        further.
        
        Well, we need to have sqrt(a) irrational in order to show
        C != 0, so let's add that to the requirements.  But with
        that addition I've only shown c nonzero implies C
        nonzero, whereas we need c positive implies C positive.
        
        Dan
1354.4GUESS::DERAMOSometimes they leave skid marks.Thu Dec 13 1990 11:587
        re .2,
        
        Yes, something like that.  I meant that if you just pull
        a, b, and c out of a hat, that the process might not
        work.
        
        Dan
1354.5TRACE::GILBERTOwnership ObligatesThu Dec 13 1990 21:107
1354.6Dan's point about origin is important, I thinkHANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Fri Dec 14 1990 20:0815
Dan's point was important, Peter, namely:

	If we start with (aqrt(a)+0)/1, we have b=0, and c=1

and he proved that given this situation, the theorem holds.  Hence you
can't start with ANY arbitrary (sqrt(a)+b)/c.

But it leads to interesting questions which I'll discuss soon, having
to do with the fact that although theorem doesn't hold in those other cases,
those other cases STILL have repeating continued fractions, so it reopens
the question of how to compute the fraction, and about whether it's
still a palindrome (probably not).

/Eric
1354.7GUESS::DERAMOSometimes they leave skid marks.Sat Dec 15 1990 04:0524
        Just work backwards from a repeating non-palindrome to
        get an example that doesn't result in a plaindrome. :-)
        
        For example, let x = [a,1,2,3,1,2,3,1,2,3,...]
        	= a + 1/(1 + 1/(2 + 1/(3 + (x-a))))
        	= a + 1/(1 + (x + (3-a))/(2x + (7-2a)) )
        	= a + (2x + (7-2a))/(3x + (10-3a))
        
        It is easy to let a = 0 when you have
        
        	x = (2x + 7)/(3x + 10)
        	3x^2 + 10x = 2x + 7
        	3x^2 + 8x - 7 = 0
        
        	x = (-8 +/- sqrt(148)) / 6
        
        The positive root is (sqrt(148) - 8)/6 = (sqrt(37) + (-4))/3
        Here c | a-b^2 (i.e., 3 | 37 - 16 or 3 | 21) so the
        process of finding the continued fraction for this x
        works but it must result in the nonpalindrome that we
        started with.  (Trust me...besides I worked it out and got
        [0,1,2,3,1,2,3,...].)
        
        Dan
1354.8GUESS::DERAMOSometimes they leave skid marks.Sat Dec 15 1990 18:295
        If you use the more general form (a sqrt(b) + c)/d then
        there shouldn't be any problems computing the continued
        fraction.
        
        Dan
1354.9how to always get the divisibility to holdHANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Mon Dec 17 1990 13:1814
I studied that number theory book a bit more.  They pointed out a simple
trick.  Suppose you have

	(sqrt(a)+b)/c

and the divisibility rule doesn't hold (as Peter showed us).  The book says
merely multiply all three terms by c, giving:

	(sqrt(acc)+bc)/(cc)

Now the divisibility rule holds, and you can proceed the same as before.

/Eric