GCD induction proof I apologize if this is a duplicate question (believe me, I've searched). This question is a part of an ungraded class warm-up exercise.
Question:
Using induction, prove that for all positive integers $x$ and $y$, that $g(x,y)$ computes the GCD of $x$ and $y$:   
$$g(x,y) = \left\{\matrix{x & \text{ if }~~~x=y\\g(x-y,y) & \text{ if }~~~ x>y\\g(x,y-x) & \text{ if }~~~x<y}\right.$$
Edit:
Since this is a piecewise function, the base case confuses me. Am I supposed to do three separate base cases here? Also, the fact that this is recursive is not helping.
The first thing I would do is the base case where x and y equals 1, so: gcd(1,1) = 1 since x=y.
From there I don't really know where to go.  
Apparently, knowing how to do this problem is a prerequisite for the class, which is stressing me out because I have never encountered an induction proof like this, and I really don't want to drop the class if I don't have to. 

What have you tried so far? What are you planning to use as your base case/cases and induction step?
Edit:
Your idea of 1,1 is on the right track, but think of the base case as being more general. The base case can be any case where the answer is easy to test, and where you can't induct any lower. Basically these are the endpoint/edge cases,
For example, take 10 and 6. g(10,6)=g(4,6)=g(4,2)=g(2,2)=2.
Another example: 15 and 5. g(15,5)=g(10,5)=g(5,5)=5.
We seem to be stopping at the g(x,y), x=y step. Which is great because that is easy to check -- of course gcd(x,x)=x.
The fact that there are three parts just means you have 3 induction steps, depending on xy, x=y. However once you get one, the other two should be easy.
