Subset of natural numbers

Number theory
Post Reply
Papapetros Vaggelis
Community Team
Posts: 426
Joined: Mon Nov 09, 2015 1:52 pm

Subset of natural numbers

#1

Post by Papapetros Vaggelis »

Let \(\displaystyle{S\in\mathcal{P}(\mathbb{N})\setminus \left\{\varnothing\right\}}\) such that the

set \(\displaystyle{\mathbb{N}\setminus S}\) is infinite. Suppose that \(\displaystyle{x\,,y\in S\implies x+y\in S}\).

Prove that there exists \(\displaystyle{n\in\mathbb{N}\,,n\geq 2}\) which divides every element of \(\displaystyle{S}\).
jason1996
Posts: 2
Joined: Sat Nov 12, 2016 3:50 pm

Re: Subset of natural numbers

#2

Post by jason1996 »

Suppose that is no $ n\in \mathbb{N}$, n>1 which divides every element of S. Then there exist $ a,b\in S$ with (a,b)=1. It is trivial to prove that for every $ k,l\in \mathbb{N}$, $ ka+lb\in S$. Let q>ab. Then if (k,l) solution of the equation ka+lb=q (1) there is either k>b or l>a.(2) Also we notice that if (k,l) solution of (1) then (k+b,l-a) is also solution of (1) This means that (1) has infinite number of solutions. Suppose that there is no solution in positive integers. Let $ (k_{1},l_{1})$ the solution where $ k_{1}$ takes the maximum negative value possible. Then $ l_{1}>0$ and also $ k_{1}+b>0$ and $ l_{1}-a<0\Rightarrow l_{1}<a\Rightarrow k_{1}>b$ (from (2)) contradiction because we defined $ k_{1}$ as negative. So for every q>ab (1) has a solution in positive integers so $ \mathbb{N}/S\subseteq \left \{ 1,2,...ab\left. \right \} \right. $ contradiction. So the proof has finished.
S.F.Papadopoulos
Posts: 16
Joined: Fri Aug 12, 2016 4:33 pm

Re: Subset of natural numbers

#3

Post by S.F.Papadopoulos »

Why there exist $a,b\in S$ with $(a,b)=1$?
Post Reply

Create an account or sign in to join the discussion

You need to be a member in order to post a reply

Create an account

Not a member? register to join our community
Members can start their own topics & subscribe to topics
It’s free and only takes a minute

Register

Sign in

Who is online

Users browsing this forum: No registered users and 5 guests