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 D1, ... ,Dm are different divisors of an integer N whose decomposition in prime factors is prodti = 1p\alphaii and each two of the d's have a common divisor > 1 then, denoting prod ti = 1\alphai = \alpha,

max m = f(N) = 1/2 sum max \left{prod\mu\nu = 1 \alphai\nu, \alpha/prod\mu\nu = 1 \alphai\nu \right}

where the summation is over all subsets {i1, ... ,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 G1, ... ,Gm 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 Gm+1, ... ,Gg(N) so that no two of the g(N) distinct divisors Gi, 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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page