Now, we shift two numbers down and do it again:

16 = 2 * 6 + 4  ...  2 )  6 = 1 * 4 + 2  ...  4 goes into 6 one time  ...  with 2 left over
 


OK, let me write this out in one chunk:

Find  GCF( 16 , 6 )


16 = 2 * 6 + 4  ...  6 = 1 * 4 + 2  ...  this 2 is the GCF  ...  4 = 2 * 2 + 0  ...  when you hit + 0, you are done!

 

GCF( 16 , 6 ) = 2

 

The GCF is always the last remainder before you get 0!