The cyclomatic complexity of the gcd function is four. In general, the cyclomatic complexity is an upper limit of the number of necessary test cases.
In the gcd function, it is possible to cover all source lines with two test cases. Notice in gcd that the control of the branches of the two if control structures are coupled.
This is actually poor programming!
This observation may imply that it is impossible to find input data that exercises all independent paths.