My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
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.
uberbandgeek6 is offline  
 
February 4th, 2010, 06:27 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.