In a division, why is every common divisor of the divisor and the remainder also a divisor of the dividend?

Question

In the GRE quantitative reasoning exam, I came across the following question: when the positive integer $n$ is divided by $45$, the remainder is $18$. Which of the following must be a divisor of $n$?

a) $11$
b) $9$ ( the correct choice)
c) $7$
d) $6$
e) $4$

The following solution was given:

The given information tells that $n$ can be expressed in the form $$n = 45k + 18 \, ,$$where $k$ is non-negative integer. Consider how the divisors of $45$ and $18$ may be related to the divisors of n. Every common divisor of $45$ and $18$ is also a divisor of any sum of multiples of $45$ and $18$, like $45k+18$. So any common divisor of $45$ and $18$ is also a divisor of n. Of the given answer choices, only $9$ is a common divisor of $45$ and $18$. Thus the correct answer is choice b).

I don't understand the emphasized part in the explanation and the whole reasoning in general. Can someone clarify it please?

Duplication disclaimer: this post requests for a different explanation than is provided in the similar post.

Answer 1

Take $n=45k+18$ . Put the factor $9$ in evidence in the right side.

$ n = 9 \cdot (5k + 2)$.

Note that $5k + 2$ is an integer, then, substituting this quantity by $m$, we have

$n = 9 \cdot m$

where $m$ is an integer. therefore, $n$ is an multiple of $9$.

Answer 2

I assume that you follow the reasoning of the solution up to the point where $n=45k+18$.

Now suppose that $d$ divides $45$ and $d$ also divides $18$. Note that $d$ divides $45k$. Therefore, $d$ divides the sum of $45k$ and $18$, i.e. $d$ divides $45k+18$.

To prove this formally, note that $d$ divides $45$ by definition means that there is an integer $m$ such that $dm=45$. Hence, $dmk=d(mk)=45k$, and so $d$ divides $45k$. Since $d$ divides $18$, there is an integer $n$ such that $dn=18$. Therefore, $dmk+dn=45k+18$. But note that $dmk+dn=d(mk+n)$, and so $d$ divides $45k+18$.

To summarise, we have proven that if $d$ divides both $45$ and $18$, then $d$ divides $n=45k+18$. Since $9$ divides $45$ and $18$, it follows that $9$ divides $n$.

Remark: One confusing point is that the word divisor has two separate meanings. If we divide the integer $a$ by the integer $b$ (where the division is with a remainder), then $a$ is called the dividend and $b$ is called the divisor. On the other hand, to say that an integer $m$ divides an integer $n$ means that there is an integer $k$ such that $mk=n$. We sometimes say that "$m$ goes into $n$" in such a situation.