The Question: We can define a set of integers $X_a$$_,$$_b$ = {∀u, v ∈ $\Bbb Z$, au + bv}. For example, if a = 6 and b = 8 then X$_6$$_,$$_8$ includes numbers like 20 = 2$*$6 + 1$*$8 and 4 = −2$*$6 + 2$*$8. Let c be the smallest positive integer in X$_a$$_,$$_b$. Prove that every number in X$_a$$_,$$_b$ is a multiple of c.


marked as duplicate by Bill Dubuque elementary-number-theory Oct 7 '18 at 1:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Have you tried by contradiction? If $c$ doesn't divide $m$, then there is a non-zero remainder... $\endgroup$ – Arnaud Mortier Oct 6 '18 at 22:36
  • $\begingroup$ @ArnaudMortier How does a non-zero remainder have any connection to X$_{a,b}$? $\endgroup$ – Cup Oct 7 '18 at 0:00

Divide the arbitrary element of $X_{a,b}$ by $c$

The reminder if not zero is a positive number less than $c$ which is also an element of $X_{a,b}$

I let you show that the remainder is indeed an element of $X_{a,b}.$

  • $\begingroup$ How to prove the remainder is an element of X$_{a,b}$? Assume X$_{a,b}$ = k$_1$a + k$_2$b, since k1 and k2 can be anything, does that mean r is an element of X$_{a,b}$ $\endgroup$ – Cup Oct 6 '18 at 22:47
  • $\begingroup$ The remainder is the difference of two elements so it is an element. Think about linear combinations. $\endgroup$ – Mohammad Riazi-Kermani Oct 6 '18 at 22:54
  • $\begingroup$ Im sorry but i still dont really understand. What would the two elements be? $\endgroup$ – Cup Oct 7 '18 at 0:06

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