3

If we are on a number line starting at 0 and we can only take steps x or y long in either direction where x and y are integers, we can only reach points that are (integer) multiples of gcd(x, y).

Apparently this is true, but I am having a hard time visualizing why we cannot reach multiples of smaller shared factors of x and y that are not multiples of the gcd.

Also, can anyone offer an intuitive explanation for why all shared factors of x and y must also be factors of their gcd? Thanks!

notReallyDev
  • 179
  • Same reason why you can only pay amounts that are a multiple of $5$ if all you had were coins of $10$ and $25$. – dxiv Aug 05 '17 at 20:05

2 Answers2

7

Since $d:=\gcd(x,y)$ divides both $x$ and $y$, then there are integers $m,n$ such that $md=x$ and $nd=y$. Thus every step of distance $x$ is $m$ steps of the gcd and similarly every step of distance $y$ is $n$ steps of the gcd. Hence, for every integers $s,t$, we have that $$ sx + ty = s(md) + t(nd) = (sm+tn)d. $$ This shows that the total distance covered is a multiple of their gcd.

John Griffin
  • 10,668
  • What if i take any other common divisor of $x$ and $y$, which is not their gcd? – Someone Jan 18 '18 at 13:27
  • @Mann The statement remains true with the same proof. However, every multiple of the gcd is a multiple of a common divisor, so the problem as stated is more general. – John Griffin Jan 18 '18 at 16:30
2

I think you can understand that a linear combinaton of multiples of units is itself a multiple of the unit whatever the unit is. A divisor of a number is like a unit and the number is itself a multiple of the unit. If numbers have a common divisor, then they have a common unit and so any linear combination is also a multiple of that unit. The GCD is a common divisor and thus the previous reasoning applies to it.

Note that the GCD of numbers is a linear combination of those numbers using the extended Euclid algorithm. Thus a a shared factor of the numbers is also a factor of the GCD.

Somos
  • 35,251
  • 3
  • 30
  • 76