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?

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

No need to consider prime factorizations.

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 $$

  • $\begingroup$ So all i have to prove is that $\frac{a}{k}s$ holds for all $s \in \mathbb{Z}$ if $k~|~a$? $\endgroup$ – obliv Apr 15 '16 at 18:33
  • $\begingroup$ @Obliv, $\frac{a}{k}$ and $s$ are integers and so $\frac{a}{k}s$ is an integer. $\endgroup$ – 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)$

  • $\begingroup$ that is much easier than what I thought I had to go through. :( $\endgroup$ – obliv Apr 15 '16 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.