Fibonacci numbers | gcd …. (Part 2)

 

The gcd of any two Fibonacci numbers is also a Fibonacci number

 

gcd \, (F_3, F_2) \; = \; gcd \, (3, 2) \; = \; 1 \; = \; F_1 \; = \; F_2

gcd \, (F_5, F_3) \; = \; gcd \, (5, 2) \; = \; 1 \; = \; F_1 \; = \; F_2

gcd \, (F_6, F_9) \; = \; gcd \, (8, 34) \; = \; 2 \; = \; F_3

gcd \, (F_6, F_{12}) \; = \; gcd \,(8,144) \; = \; 8 \; = \; F_6

gcd \, (F_7, F_{14}) \; = \; gcd \,(13,377) \; = \; 13 \; = \; F_7

gcd \, (F_m, \; F_n) \; = \; F_{gcd \,(m,n)}
 
 

->   gcd \, (F_n, \; F_{n-1}) \; = \; 1   for all   n

->   F_{m+n} \; = \; F_{m+1} \, F_n \; + \; F_m \, F_{n-1}

->   if   m   divides   n,   then   F_m   divides   F_n
         If   n = qm + r,   then   gcd \,(n,m) \; = \; gcd \,(m,r)
         For such   n, m   we have

gcd \,(F_m, \; F_n)
= \; gcd \,(F_m, \; F_{qm + r})
= \; gcd \,(F_m, \; F_{qm+1} \, F_r \; + \; F_{qm} \, F_{r-1})
= \; gcd \,(F_m, \; F_{qm+1} \, F_r)
= \; gcd \, (F_m, \; F_r)

gcd \,(F_m, \; F_n) \; = \; gcd \, (F_m, \; F_r)

 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 

Advertisements

About benvitalis

math grad - Interest: Number theory
This entry was posted in Number Puzzles and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s