Cardinality of subsets of the residue group with nonunit differences of elements

P. V. Roldugin

Diskretnaya Matematika, Tome 28 (2016) no. 3, pp. 111-125

Résumé

The paper is concerned with the subsets $I\subset\left\{ {0,\;\ldots,\;d - 1} \right\}$ for which gcd$\left( {n - m,\;d} \right) \ne 1$ for any $n,\;m \in I$. Such subsets are called sets of nontrivial differences. Let $d > 1$ and ${d_1}$ be the least prime divisor of $d$. We prove that the largest cardinality of a set of nontrivial differences is $d/{d_1}$. Sets of nontrivial differences in which not all differences of elements are multiples of the same prime factor $d$ are called nonelementary. Let $t$ be the number of prime factors of $d$. We show that there are no nonelementary sets for $t \leqslant 2$. It is shown that a minimal nonelementary set may have arbitrary order in the interval $\overline {3,\;t} $. The largest cardinality of nonelementary sets is estimated from below and above.

Détail

Keywords: residue group, differences of elements, nonunit elements, subset cardinality.