Let $A$ be a set of positive integers satisfying the following properties: (i) if $m$ and $n$ belong to $A$, then $m+n$ belong to $A$; (ii) there is no prime number that divides all elements of $A$.

(a) Suppose $n_1$ and $n_2$ are two integers belonging to $A$ such that $n_2-n_1 >1$. Show that you can find two integers $m_1$ and $m_2$ in $A$ such that $0< m_2-m_1 < n_2-n_1$

(b) Hence show that there are two consecutive integers belonging to $A$.

(c) Let $n_0$ and $n_0+1$ be two consecutive integers belonging to $A$. Show that if $n\geq n_0^2$ then $n$ belongs to $A$.

  • $\begingroup$ Have you tried anything? $\endgroup$ – Patrick Stevens Nov 19 '16 at 11:38
  • $\begingroup$ Not familiar with this type of question; where can i find this type of questions for practice? $\endgroup$ – user365928 Nov 19 '16 at 11:39
  • $\begingroup$ I more meant "do you have any thoughts about how to tackle the question" than "have you seen anything similar before". $\endgroup$ – Patrick Stevens Nov 19 '16 at 11:40
  • $\begingroup$ artofproblemsolving.com/community/c6h474320p2656536 $\endgroup$ – user365928 Nov 19 '16 at 11:42
  • 3
    $\begingroup$ A nice problem that deserves an upvote, but not without your thoughts and efforts. $\endgroup$ – ajotatxe Nov 19 '16 at 11:54

Some hints:

  • For a) you should consider Bezout's identity. Note that if $n\in A$ then every multiple of $n$ is also in $A$.
  • For b) use induction.
  • For c), let $n\ge n_0^2$ and let $k=n-n_0^2$. Use Euclidean division to write $k=qn_0+r$. Then $n=n_0((q+1)n_0-r)+r(n_0+1)$.

Lemma 1: if gcd(A, B) = 1 then for any X>=A*B x=k1*B +k2*A, k1,k2 >=0

Lemma 2 X, Y in N, gcd(X, Y) = K Exists k1: for any k>=k1 K*k in N (from lemma 1)

Prove what min{gcd(X,Y)| X, Y in A} = 1 Let this min is K = K1*P, gcd(X, Y) = K

Get Z in N, P not divide Z, max prime divisor of Z is P1 Let P2 is prime, P2>P1, P2*K in A (by lemma 2) gcd(p2*K, Z) = gcd(K, Z) = gcd(K1*P, Z) = gcd(K1, Z) <=K1 < K - it is contrexample.

So, we can find in A X and Y what gcd(X, Y) = 1 => XY in A and XY+1 in A (lemma 1) => QED

it is (a) and (b)

C is simply lemma 1


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy