Define a finite set $A$ to be 'good' if it satisfies the following conditions: (a) For every three disjoint element of $A,$ like $a,b,c$ we have $\gcd(a,b,c)=1;$ (b) For every two distinct $b,c\in A,$ there exists an $a\in A,$ distinct from $b,c$ such that $bc$ is divisible by $a.$ Find all good sets.
Problem
Source: Iran TST 2011 - Day 2 - Problem 1
Tags: number theory, relatively prime, number theory unsolved
10.05.2011 20:25
goldeneagle wrote: we call a finite set like $A$ good if: 1)for every three disjoint element of $A$ like $a,b,c$ we have:$ \gcd(a,b,c)=1$ 2)for every two disjoint $b,c\in A$ exist disjoint $a\in A$ such that $bc$ is divisible by $a$ find all good sets. Set $gcd(a,b)=p,gcd(b,c)=r,gcd(a,c)=q$ ( it can't $a$ has a prime factor who isn't in $b$ and $c$ or $a \not|bc$ hence $a=pq$ we see easy) and we find first triplet $(pq,pr,qr)$ every other number has is distinct with $p,q,r$ and hence can't exist. Hence $(pq,pr,qr)$ which are per 2 relative prime are all sets.
10.05.2011 20:40
SCP wrote: Set $gcd(a,b)=p,gcd(b,c)=r,gcd(a,c)=q$ ( it can't $a$ has a prime factor who isn't in $b$ and $c$ or $a \not|bc$ hence $a=pq$ we see easy) Could you please explain, why you obtain from here that $a=pq$.
10.05.2011 20:43
sandu2508 wrote: SCP wrote: Set $gcd(a,b)=p,gcd(b,c)=r,gcd(a,c)=q$ ( it can't $a$ has a prime factor who isn't in $b$ and $c$ or $a \not|bc$ hence $a=pq$ we see easy) Could you please explain, why you obtain from here that $a=pq$. $p,q|a$ and $ggd(p,q)=1$ or otherwise $gcd(a,b,c)>1$ and $a$ hasn't other primefactors not in $gcd(a,b)*gcd(c,a)$ hence result.
10.05.2011 20:46
SCP wrote: $p,q|a$ and $ggd(p,q)=1$ or otherwise $gcd(a,b,c)>1$ and $a$ hasn't other primefactors not in $gcd(a,b)*gcd(c,a)$ hence result. Thank you.
12.05.2011 05:04
If the set contains at most one element, the statement obviously holds. Assume it has two elements, by condition 2, there is a third element. Take two smallest elements b,c and another element a such that a divides bc. Let p=(a,b), q=(a,c), r=(b,c). We can write a=pqx, b=pry, c=qrz, where (qx,ry)=(py,qz)=(rz,px)=1. So x divides r^2 yz, but they are coprime, hence x=1. Suppose another element d divides ab=p^2 yqr. By condition 1, d is coprime to p,q,r, so p divides y. But this implies that d is smaller than b, a contradiction. Similarly, no other element can divide ac. So b divides ac and c divides ab, that gives y=z=1, so (a,b,c)=(pq,pr,qr). Assume there are other elements, take the smallest one, m. By condition 1, m is coprime to p,q,r. If am is divisible by another element (not b,c), this element must divide m, a contradiction. So b or c (wlog b) divides am, this implies r=1, but then no element can divide bm, a contradiction. Therefore, there is no other elements. Answer: {}, {n}, {pq,qr,pr} where p,q,r are pairwise coprime.
12.05.2011 11:49
Take $c$ to be the smallest integer in $A$, Assume that $|A|>3$. Let $b$ be an element of $A$, so there exist $a$ so that $a|bc$ and $d$ so that $d|ac$. if $(d,a)=1$ then, $d|c$ which is absurde. Let $p$ be a prime divisor of $(a,d)$. So $p|a|bc$ which implies that $p|c$ or $p|b$ meaning that $(a,d,c)>1$ or $(a,d,b)>1$ which is absurde, hence $|A|=3$. Now let $p=(b,c)$ and put $b=pq$ and $c=pr$ with $(q,r)=1$, we get then $a|qr$ , $q|ar$ and $r|aq$ whihc yields to $a=qr$. From here it's easy to deduce that $A=\{pq,qr,rp\}$ where $p$ , $q$ and $r$ are pairwise relatively prime integers.
16.05.2011 20:28
The problem is proposed by Mohammad Mansouri.
12.06.2021 16:50
Apparently I overcomplicated it Answer. All sets of the form $(a, b, ab)$ with $(a, b)=1$ and $(pq, qr, rp)$ where $p, q, r$ are pairwise relatively prime integers. Proof. Suppose $|A|\ge 4$. Consider the smallest element $c$ of $A$. Using the choice of $c$ observe that for any $a$ in $A$ there's a $b$ such that $(a, b)>1$, where $a, b\neq c$. Let $A:=\{a_{1}, a_{2}, \dots, a_{n}\}$ and let $a_1=c$. Consider the chain $ca_{2}\to ca_{3}\to \cdots \to ca_{n}$ of dividends and distinguish $2$ cases. Case 1. For some $a_{i}, a_{j}\in A$ other than $c$ there exists an $a\in A$ $(a\neq c, a_{i}, a_{j})$ such that $a\mid ca_{i}$ and $a\mid ca_{j}$. $\bullet$ Then $a\mid c\cdot (a_{i}, a_{j})$ and since $c<a$ there's a prime $p\mid a$ that $p\mid (a_{i}, a_{j})$ , contradiction. Case 2. $\forall a_{i}\in A$ the number $a_j$ dividing $ca_{i}$ is different than that of the others. $\bullet$ Let \begin{align*} a_{i_2}\mid ca_{2}\hspace{2 mm} \cdots \hspace{2 mm} a_{i_n}\mid ca_n\end{align*}Then there's a permutation $(j_2, \dots, j_n)$ of $(i_2, \dots, i_n)$ such that \begin{align*} a_{i_2}\mid c^{2}a_{j_2}\hspace{2 mm} \cdots \hspace{2 mm} a_{i_n}\mid c^{2}a_{j_n}\end{align*}And if for all $2\le i\le n$ any prime $q\mid a_i$ divides $c$, then since there're $a_{i}, a_{j}$ with $(a_i, a_j)>1$, we can find a prime $q\mid a_i, a_j, c$ , absurd.