My Math Forum  

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

Number Theory Number Theory Math Forum

LinkBack Thread Tools Display Modes
February 4th, 2010, 04:03 AM   #1
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  

  My Math Forum > College Math Forum > Number Theory

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.