From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Sun Apr  6 22:01:20 2008
Date:         Sun, 6 Apr 2008 22:01:06 -0400
From: "William J. Rapaport" <rapaport@cse.Buffalo.EDU>
Subject: 191: Fibonacci and GCD
To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU

------------------------------------------------------------------------
Subject: 191: Fibonacci and GCD
------------------------------------------------------------------------

My Ph.D. student, Albert Goldfain, recently pointed out to me that:

	GCD(Fib(m),Fib(n)) = Fib(GCD(m,n))

where "Fib" is the Fibonacci function such that Fib(n) = the nth
Fibonacci number, and "GCD" is the greatest common divisor function such
that GCD(x,y) = the largest integer that divides both x and y.  (You
explored GCD in HW #9.)

So, this theorem says that the greatest common divisor of any two
Fibonacci numbers is the kth Fibonacci number, where k = GCD(m,n).

I find that pretty amazing.  For more information on this, including
proofs (inductive, of course!), see: 

Su, Francis (2007), "Fibonacci GCD's, please", in Mudd Math Fun Facts:
http://www.math.hmc.edu/funfacts/ffiles/20004.5.shtml

Dahlke, Karl (2008), "Difference Equations, The Fibonacci Sequence",
in Math Reference Project:
http://www.mathreference.com/num-deq,fib.html

Solovay, Robert M. (2002), "Fibonacci Numbers", (*)
Journal of Formalized Mathematics, Vol. 14
http://www.cs.ualberta.ca/~piotr/Mizar/mirror/http/JFM/Vol14/fib_num.html

	(*) This is an odd article, written in a highly formalized version
	    of English intended to be comprehensible to any mathematician.
	    For more information on the formal language, called "Mizar",
	    see:
	    http://www.cs.ualberta.ca/~piotr/Mizar/mirror/http/language/