I understand GCD mathematically but i can't figure out where to apply it. For eg I saw this problem today:
Adam is standing at point $(a,b)\in\mathbb Z^2$ in an infinite 2D grid.
He wants to know if he can reach point $(x,y)$ or not.
The only operations he can do is to move to the points $(a+b,b), (a,a+b), (a-b,b)\text{ or }(a,a-b)$ from some point $(a,b)$.
It is given that he can move to any point on this 2D grid, i.e. the pointscan have positive or negative $x$(or $y$) coordinates.Tell Adam whether he can reach $(x,y)$ or not.
The solution to this problem is simple:
If $\gcd(x,y) = \gcd (a,b)$ then adam can reach $(x,y)$ from $(a,b)$, otherwise not.
While this solution is indeed working I am not able to figure out how to come up with it. What is the significance of $\gcd$ in this question?
The crucial observation is that $\gcd(u,v)=\gcd(v,u)=\gcd(u,u\pm v)$.
From this follows Euclid's algorithm for computing gcd.
The significance of the gcd in your problem is that the crucial observation implies that all points visited by allowed moves have the same gcd. So, you can divide their coordinates by that gcd and reduce the problem to a grid with unit spacing and whose allowed moves are to immediate neighbors.
The crucial observation proves that if $(x,y)$ is reachable from $(a,b)$,then $\gcd(x,y)=gcd(a,b)$.
For the converse, note that the set of all points that are reachable from $(a,b)$ have coordinates of the form $am+bn$, with $m,n\in\mathbb Z$. The set of all such linear combinations is the set of all multiples of $\gcd(a,b)$.