##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 222.05007

**Autor: ** Erdös, Paul; Schönheim, J.

**Title: ** On the set of non pairwise coprime divisors of a number. (In English)

**Source: ** Combinat. Theory Appl., Colloquia Math. Soc. János Bolyai 4, 369-376 (1970).

**Review: ** [For the entire collection see Zbl 205.00201.]

Theorem 1. If D_{1}, ... ,D_{m} are different divisors of an integer N whose decomposition in prime factors is **prod**^{t}_{i = 1}p^{\alphai}_{i} and each two of the d's have a common divisor > 1 then, denoting **prod** ^{t}_{i = 1}\alpha_{i} = \alpha, **max** m = f(N) = ^{1}/_{2} **sum** **max** \left**{****prod**^{\mu}_{\nu = 1} \alpha_{i\nu}, \alpha/**prod**^{\mu}_{\nu = 1} \alpha_{i\nu} \right**}** where the summation is over all subsets **{**i_{1}, ... ,i_{\mu} **}** of **{**1, ... ,t **}** and for the empty subset the product is considered to be one. The result is best possible, for every N there are f(N) divisors no two of which are relatively prime. Theorem 2. Let G_{1}, ... ,G_{m} be m distinct divisors of N not two of which are relatively prime. Assume m < g(N). Then there are g(N)-m further divisors G_{m+1}, ... ,G_{g(N)} so that no two of the g(N) distinct divisors G_{i}, 1 \leq i \leq g(N) are relatively prime. Theorem 2 is best possible.

**Classif.: ** * 05A17 Partitions of integres (combinatorics)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag