Let $ A$ be the subset of the set of positive integers, having the following $ 2$ properties: 1) If $ a$ belong to $ A$,than all of the divisors of $ a$ also belong to $ A$; 2) If $ a$ and $ b$, $ 1 < a < b$, belong to $ A$, than $ 1 + ab$ is also in $ A$; Prove that if $ A$ contains at least $ 3$ positive integers, than $ A$ contains all positive integers.
Problem
Source:
Tags: induction, modular arithmetic, number theory, combinatorics proposed, combinatorics
05.03.2009 01:42
If $ A$ contains $ 1$ and $ a,b$, then it will contains with confidence $ 2$, too. Simply, if $ a$ and $ b$ aren't even, then $ ab + 1$ would be such one $ \Rightarrow 2\in A$. By induction we can prove that the elements of $ A$ leap through all the remainders $ \mod 2^n$ for some nature $ n$ and using this fact we would be able to complete the solution very quickly. 1. Obviously for $ n = 1$, we will have some evens and some odds, hence we needn't prove anything. 2. Let's suppose we have proved that for $ n = k$ there always exists $ a\in A$ such that $ a\equiv r(\mod 2^k)$ for every $ r = 0,1,2\dots, 2^k - 1$. Let's now look $ n = k + 1$: If $ a = 2^kq + r\in A$ for $ 0\le r < 2^k$, $ \Rightarrow 2a + 1 = 2^{k + 1}q + 2r + 1 = c\in A$ for some odd $ 1\le 2r + 1 < 2^{k + 1}$. Now let us get $ c_1\equiv 2r - 1$ and $ c_2\equiv 1$ $ (\mod 2^{k + 1})$, $ \Rightarrow c_1c_2 + 1\equiv 2r(\mod 2^{k + 1})$ and we are ready. After we have this, it remains to prove that every even belongs to $ A$ and the rest is elementary.
05.03.2009 04:52
To get $ \pmod m$, use the command \pmod{m}.
06.03.2009 21:14
I have a different solution to this one. Easy to prove that numbers $ 1$ and $ 2$ belong to $ A$.Let's show that $ 3$ is also in set $ A$. Assume that the next positive integer is $ p$, where $ p$ is a prime number. (If $ p$ is composite and not of the form $ 2^{n}$, than it must have the prime divisor more than $ 2$, but if it's $ 2^{n}$, than $ 2^{n + 1} + 1$ is also contained in $ A$ and it undoubtedly has prime divisor). If $ p = 3k + 1$, for some positive $ k$, than $ 2(3k + 1) + 1 = 3(2k + 1)$ is in $ A$, implying that $ 3$ is in $ A$ as well. Assume $ p = 3k + 2$. Obviously, all the numbers of the form $ 2^{n}(p - 1) + 1$ are contained in $ A$. It means that if $ 3$ is not in $ A$, than all of the divisors of $ 2^{n}(p - 1) + 1$ must be of the form $ 3k + 2$. But if it has two divisors of this form, or has a divisor in greater degree than $ 2$, it will obviously have one with form $ 3k + 1$. So, remaining case is when all of the numbers of the form $ 2^{n}(p - 1) + 1$ are prime, but if $ n = p - 1$, we have $ p|2^{n}(p - 1) + 1$(By Fermat's little theorem), where $ 2^{n}(p - 1) + 1 > p$, implying that $ 2^{n}(p - 1) + 1$ is composite, q.e.d. So $ 3$ is in $ A$. We can easily get that $ 4$ and $ 5$ are also elements of the set $ A$. Let's use induction to prove the following claim: If $ n > 5$ and the set $ S = {1,2,3,...,n - 1}$ is subset of $ A$, than $ A$ contains $ n$. Proof: If $ n$ is odd, $ 2\frac {n - 1}2 + 1 = n$ is in $ A$, q.e.d. If $ n$ is even, $ 2\frac {n}{2} + 1 = n + 1$ is in $ A$. Hence, $ (n + 1)(n - 1) + 1 = n^{2}$ is in $ A$, giving $ n$ is in $ A$, q.e.d. This ends our proof. Lasha Lakirbaia.
20.12.2013 09:38
lasha wrote: Obviously, all the numbers of the form $ 2^{n}(p - 1) + 1$ are contained in $ A$. How to get this?
23.07.2014 03:04
It is trivial to prove that numbers $ 1,2 $ belong to $ A $.It is not that hard for $ 3 $ neither.$ 4 $ goes easily too.Just suposse oposite and examine cases which easily lead to contradiction.Now suposse otherwise,that there exist some numbers that don't belong to $ A$.Let $ k $ be the smallest one of them.Now because $ k>4 $ it holds $ \frac{k}{2} $ is not equal to $ 2 $.So if we take $ a=2 $ and $ b=\frac{k}{2} $ we easily obtain that $ A $ has $ ab+1=k+1 $ in itself.Now taking $ a=k-1 $ and $ b=k+1 $ we obtain $ A $ has $ ab+1=(k-1)(k+1)+1=k^2-1+1=k^2 $ so $ A $ contains $ k $ too,so we have that $ A $ contains all positive integers for $ 2|k $.Now if that isn't the case we will have to prove that $5$ belongs to $A$ and then we would have that $ \frac{k-1}{2}>2 $ so by taking $ a=2 $ and $b=\frac{k-1}{2}$ we obtain that $k$ belongs to $A$ which is a contradiction so the task is proved.
23.07.2014 03:10
Actualy,i will write the part for $ 3 $ as well: Suposse there are numbers $ 1,2,p $ in $ A $ such that $ p $ is prime (it is easy because there can't only be number $2$).Now if $ p \equiv 1 \pmod {3} $ it is trivial.Now consider case $ p \equiv 2 \pmod {3} $.Because of this $ A $ will have in itself also number $ 2p+1 $ which implies that it will also contain number $ 2p^2 + p + 1 $. It is clear that this number is not prime because $ p $ isn't equal to $ 2 $.So it has more than one divisor.Now it is trivial by just considering possible divisors.
23.07.2014 15:48
An easy problem.We easy obtain that the sequence has 2(if all are odd then 1+ab will be even),and it has 3(if we have two integrs such that they are not congruent to each other mod3,we are finished,now,suppose that all are congruent to each other mod 3,now it is trivial that if all are 1 mod 3,so let all of them be 2 mod3,now if we have an even number bigger then 2 congruent to 2 mod3,than that number has a divisor bigger than 1 congruent to 1,so if all are odd and 2 mod 3,than 1+ab is even and 2 mod3,so we are finished),now from 2 and 3 we obtain 7 and then 5 and use that if a and a+2 belong to A,then a+1 belongs to A,and now we have 2,3,4,5,6 and 7,and now it is easy to see we are finished(induction)
01.02.2016 15:43
First , we'll prove that $1$ (trivial) , $2,3,4$ belong to the set . -For $2$ :Suppose one of the elements is even , then $2$ blongs to the set since it divides that element . Otherwise , if all the elements are odd then $ab+1$ must be even for some $a,b$ and so $2$ belongs eitherways. -For $3$: If one of the elements is divisible by $3$ we're done . Otherwise suppose out of the three elements , two are not congruent to eachother mod 3 , then their product is congruent to 2 mod 3 , increased by $1$ is divisible by $3$ . Now suppose a=b=c=/=0[3] , then ab+1=bc+1=ac+1=2[3] , and so considering the new element $ab+1$ , we treat two cases , either a=1[3] and so a(ab+1) +1 is divisible by 3 . Or a=2[3] in wich case all of the current elements of the set are 2 mod 3 , now take an element from the set , wich has more than two divisors (obviously exists ) , either this element has a divisor congruent to 1 mod 3 , or it is a product of even number of numbers congruent to 2 mod 3 , in the latter case we simply take away one factor congruent to 2 mod 3 and we get a divisor call it $p$ (so it belongs to the set since it divides an element from teh set) and p has an odd number of divisors 2 mod 3 and so its 1 mod 3 . and now we can just take the number pa+1 wich is divisible by 3 , and so 3 belongs to the set . And now easy to prove that 4,5,6,7 .. belong by just plugging in . We generalize by induction . Suppose we proved stuff for numbers less than $X$ . If $X$ is odd then $\frac{X-1}{2}$ belongs and so $2.\frac{X-1}{2}+1=X$ also belongs . If $X$ is even then $\frac{X}{2}.2+1=X+1$ belongs and so $(X-1)(X+1) +1=X^2=0[X]$ belongs to the set and so does $X$ .
02.02.2016 15:05
If $n$ is in the set then $n-1$ is in the set. Note $n\equiv 1\pmod {n-1}$ . Take $nk+1$ for any $k$, this new term(let it be $k_1$) will be $\equiv k\pmod {n-1}$. Take $k_1$ with $n$ and we get a term $\equiv k+1\pmod {n-1}$. Repeating we will eventually get a term $\equiv 0 \pmod{n-1}$, hence $n-1$ is in the set too.
05.06.2018 16:21
A very beautiful solution:- A must contain 1(obvious) and it contains other 2 element x,y (say) so it must contain x+1( property 2) and similarly all the elements greater than x So now it is suffice to show that it contains 2,3,4....(x-1) Observe that 2x,3x,4x......(x-1)x are in the set so is it's factors ie 2,3,4.... are also in A QED