# Proving that a common divisor of two variables is also a divisor of the sum of the two variables

if $k~|~a$ and $k~|~b$ then $k~|~as+bt$ for all $s,t \in \mathbb{Z}$

is what I'm trying to prove so I thought I should start by proving that $k~|~a+b$ if $k~|~a$ and $k~|~b$.

since $a = \prod p_i^{\alpha_i}$ and $b = \prod p_i^{\beta_i}$ $k$ must be a product of primes or a prime itself. $\frac{ab}{k} = \frac{\prod p_i^{\alpha_i+\beta_i}}{\prod p_i^{\delta}}$ where $\delta \leq \alpha$ and $\delta \leq \beta$

so $\frac{a+b}{k} = \frac{\prod p_i^{\alpha_i}+\prod p_i^{\beta_i}}{k}$ is true. This is also true when $\frac{as+bt}{k} = \frac{(\prod p_i^{\alpha_i})s+(\prod p_i^{\beta_i})t}{k}$. Is this good enough?

• Actually, I'm not sure that $\delta \leq \alpha$ or $\beta$ has to be true – obliv Apr 15 '16 at 18:26
• You've got : $k | a ,b$ , then if $k | as + bt$ <=> $k | as , bt$ <=> $k | a ,b$. – openspace Apr 15 '16 at 18:30

Following your idea of using fractions, we have: $$\frac ak \in \mathbb Z, \quad \frac bk \in \mathbb Z \quad \implies \quad \frac{as+bt}{k} = \frac ak s + \frac bk t \in \mathbb Z$$
• So all i have to prove is that $\frac{a}{k}s$ holds for all $s \in \mathbb{Z}$ if $k~|~a$? – obliv Apr 15 '16 at 18:33
• @Obliv, $\frac{a}{k}$ and $s$ are integers and so $\frac{a}{k}s$ is an integer. – lhf Apr 15 '16 at 18:35
If $k|a; k|b$, then $a=km; b=kl$ where $m,l \in \mathbb Z \Rightarrow as+bt =kms+klt=k(ms+lt) \Rightarrow k|(as+bt)$