 Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd.We ignored the quotient in each step except to notice when the remainder reached 0, signalling that we had arrived at the answer.Formally the algorithm can be described as