Fibonacci numbers exhibit striking patterns. Here’s one that may not be so obvious, but is striking when you see it. Recall the\u00a0Fibonacci\u00a0numbers:<\/p>\n\n\n\n
\u00a0n: 0, 1, 2, 3, 4, 5, 6, 7,\u00a08,\u00a09, 10, 11, \u00a012, \u00a013, \u00a014, …\u00a0 Now let’s look at some of their greatest common divisors <\/p>\n\n\n\n (gcd’s): gcd(f10<\/sub>, f7<\/sub>) = gcd(55, 13) = 1 = f1<\/sub> Do you see the pattern? The greatest common divisor of any two Fibonacci numbers is also a Fibonacci number! Which one? If you look even closer, you’ll see the amazing general result:<\/p>\n\n\n\n gcd(fm<\/sub>, fn<\/sub>) = fgcd(m, n)<\/sub>.<\/p>\n\n\n\n Presentation Suggestions:<\/strong> The\u00a0Math\u00a0Behind\u00a0the\u00a0Fact:<\/strong> and the ever important Euclidean Algorithm which states: if n= qm + r, then gcd(n, m) = gcd(m, r). For such n,m we have<\/p>\n\n\n\n gcd(fm<\/sub>, fn<\/sub>) = gcd(fm<\/sub>, fqm+r<\/sub>) = gcd(fm<\/sub>, fqm+1<\/sub>fr<\/sub> + fqm<\/sub>fr-1<\/sub>) = gcd(fm<\/sub>, fqm+1<\/sub>fr<\/sub>) = gcd(fm<\/sub>, fr<\/sub>)<\/p>\n\n\n\n where the 2nd equality follows from (b), the 3rd equality from (c) noting that m divides qm, and the 4th equality from noting that fm<\/sub>\u00a0divides fqm<\/sub>\u00a0which is relatively prime to fqm+1<\/sub>. Thus<\/p>\n\n\n\n gcd(fn<\/sub>, fm<\/sub>) = gcd(fm<\/sub>, fr<\/sub>)<\/p>\n\n\n\n which looks a lot like the Euclidean algorithm but with f’s on top! For example since <\/p>\n\n\n\n gcd(100, 80) = gcd(80, 20) = gcd(20, 0) = 20, then How to Cite this Page:<\/strong> Fun Fact suggested by:<\/strong> Fibonacci numbers exhibit striking patterns. Here’s one that may not be so obvious, but is striking when you see it....<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[76,104,4,10,49],"class_list":["post-423","page","type-page","status-publish","hentry","tag-fibonacci","tag-greatest-common-divisor","tag-medium","tag-numtheory","tag-prime"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/423","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/comments?post=423"}],"version-history":[{"count":3,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/423\/revisions"}],"predecessor-version":[{"id":1326,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/423\/revisions\/1326"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/media?parent=423"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/tags?post=423"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
fn<\/sub>: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …<\/p>\n\n\n\n
gcd(f6<\/sub>, f9<\/sub>) = gcd(8, 34) = 2 = f3<\/sub>
gcd(f6<\/sub>, f12<\/sub>) = gcd(8, 144) = 8 = f6<\/sub>
gcd(f7<\/sub>, f14<\/sub>) = gcd(13, 377) = 13 = f7<\/sub>
gcd(f10<\/sub>, f12<\/sub>) = gcd(55, 144) = 1 = f2<\/sub><\/p>\n\n\n\n
After presenting the general result, go back to the examples to verify that it holds. You may wish to prepare a transparency beforehand with a table of Fibonacci numbers on it, so you can refer to it throughout the presentation.<\/p>\n\n\n\n
The proof is based on the following lemmas which are interesting in their own right. All can be proved by\u00a0induction.\u00a0
a) gcd(fn<\/sub>, fn-1<\/sub>) = 1, for all n\u00a0
b) fm+n<\/sub>\u00a0= fm+1<\/sub>\u00a0fn<\/sub>\u00a0+ fm<\/sub>\u00a0fn-1<\/sub>\u00a0
c) if m divides n, then fm<\/sub>\u00a0divides fn<\/sub>\u00a0<\/p>\n\n\n\n
gcd(f100<\/sub>, f80<\/sub>) = gcd(f80<\/sub>, f20<\/sub>) = gcd(f20<\/sub>, f0<\/sub> = 0) = f20<\/sub>.<\/p>\n\n\n\n
Su, Francis E., et al. “Fibonacci GCD’s, please.” Math Fun Facts<\/em>. <http:\/\/www.math.hmc.edu\/funfacts>.<\/p>\n\n\n\n
Arthur Benjamin <\/p>\n","protected":false},"excerpt":{"rendered":"