educative.io

Educative

Greatest Common Divisor (Euclid's Algorithm)

  • Let us suppose, a = bq + r.
  • Let d be any common divisor of a and b , which implies d | a and d | b implies that d | (a – bq), which in turn implies that d | r.

In Greatest Common Divisor (Euclid’s Algorithm) section, the above two points are there. I didn’t understand how d | a and d | b implies that d | (a – bq).

Can someone please explain.