GCD Strongly Polynomial Time
The GCD can be computed in polynomial time. Strongly Polynomial is a much more restrictive classification. Taking the definition from here:


  An algorithm runs in strongly polynomial time if
  
  
  the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input
  instance; and
  the space used by the algorithm is bounded by a polynomial in the size of the input.
  


The input to GCD is two integers. Thus, in order to be solvable in strongly polynomial time, GCD would need to be solvable with a constant number of aritmethic operations since the input size is constant.