
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
February 4th, 2010, 04:03 AM  #1 
Newbie Joined: Sep 2008 Posts: 5 Thanks: 0  Proof of a subset of integer numbers and linear combinations
Assume that the set S is a subset of integer numbers. Assume it has a property that if numbers x and y belong to S then their integer linear combination nx + my also belongs to S. Prove that either S consists from one number zero or there is a positive number d such that any other number in S is proportional to d. I already proved that it consists only of zero when x=y=0 and that otherwise there is a positive number that belongs to S, but I can't figure out how to prove the last part. I'm pretty sure that d must be the gcd, but I'm not sure if I have to prove that too. 
February 4th, 2010, 06:27 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Proof of a subset of integer numbers and linear combinations
I'm not sure what you say you've proved. It consists only of zero, except when it doesn't? How about this: for every x, y in S, x  y is in S (because their linear combination with (n, m) = (1, 1) is in S). Following the Euclidean algorithm, you can see that gcd(x, y) is in S. 

Tags 
combinations, integer, linear, numbers, proof, subset 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
need help on the proof of the inf on a subset!!  munjo5746  Real Analysis  2  June 7th, 2013 06:20 PM 
How many subset requires to cover all numbers from set  santosingh  Advanced Statistics  1  May 16th, 2012 04:58 PM 
Subset Divisibility proof  jstarks4444  Number Theory  1  October 31st, 2011 02:30 PM 
linear combinations  kiwifruit  Linear Algebra  1  January 10th, 2010 01:16 PM 
example of a subset of real numbers with two accumulationpts  boxerdog246  Real Analysis  3  October 6th, 2008 10:35 AM 