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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Oct 7 '18 at 1:07

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