The largest number which divides two numbers n and m is called the greatest common divisor of n and m, and denoted gcd(n, m).

Using Euclid's Algorithm is easy, just follow the steps shown below.

1. Write down both n and m
2. Write the larger as a number + something times the smaller
3. Repeat step 2 until the result is zero
4. The number in the row with the final 0 is the GCD of n and m

	  340                 245
	  340-245=95          245
	   95                 245
	   95                 245=55+2*95
	   95                  55
	   95=40+1*55          55
	   40                  55
	   40                  55=15+1*40
	   40                  15
	   40=10+2*15          15
	   10                  15
	   10                  15=5+1*10
	   10                   5
	   10=0+2*5             5
	    0                   5

1st Number    2nd Number      GCD