If A was {3;6;9;31}, then what would B be?

For $A=\{3,6,9,31\}$, choose $B=\{6,9,31\}$. (Note that the second condition is trivial for $a\in B$: you pick $b=a$. So you just need to check $a\in A\setminus B$.)

Let $P$ be the (partial) order on $A$ representing $a | b$, and let $Q$ be the order representing $a+1 | b+1$. We propose an algorithm to produce the set $B$. First let $M_1$ be the $P$-maximal elements in $A$. Define $B_1$ to be the $Q$-minimal elements in $M_1$, then $B_1$ satisfies the first condition and furthermore $B_1$ "Q-dominates" $R_1 = M_1-B_1$. Next let $M_2$ be the $P$-maximal elements in $A-R_1$, define $B_2$ to be the $Q$-minimal elements in $M_2$ and $R_2 = M_2- B_2$. Importantly, note that $M_2$ includes $B_1$. Since $B_2$ $Q$-dominates $M_2$ by choice, we deduce by transitivity that $B_2$ $Q$-dominates $R_1$ and $R_2$. Next let $M_3$ be the $P$-maximal elements in $A-R_1-R_2$, so on and so forth. This process must stop at a point when $R_k$ is the empty set. Let $A^* = A - R_1-R_2-...-R_{k-1}$. Then by our choices $B_k$ is $P$-maximal in $A^*$. Moreover the elements in $B_k$ are $Q$-independent since $R_k$ is empty. Finally $B_k$ $Q$-dominates $R_1 \sim R_{k-1}$ by generalizing the argument we used to show $B_2$ dominating $R_1$. Hence $B_k$ satisfies both desired conditions.

Here's a proof by induction on the numbers of elements of A Let C(A) be the number of elements of A. For C(A)=1 the statement is of course true Suppose the statement is true for any set A with C(A)=n If we add a new element x in A , to make things simpler we can divide the elements which compose the set B relative to the set A when still x hadn't been added, into two sets B+, composed by all the elements of B greater than x , and B-, composed by all the elements of B smaller than x. If there is at least one element( b+) of B+ such that x divides (b+), or at least one element (b-) of B- such that (b-)+1 divides x+1, we can add x to A/B and we are done. Otherwise, suppose we cannot add B because of the conditions given by the problem, and suppose D is the subset of B which is composed by all and only the elements of B which make it impossible for x to join B. Then we define B'=(B/D)+{x}. It's easy to verify that B' is a valid set B for A+{x}. Thus the statement is true for every positive integer value of C(A) and we are done. Edit: of course using induction doesn't really change the nature of the proof