Geodesic
Cardinality of subsets of the residue group with nonunit differences of elements
Diskretnaya Matematika, Tome 28 (2016) no. 3, pp. 111-125 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Mots-clés : residue group
Keywords: differences of elements, nonunit elements, subset cardinality. 
@article{DM_2016_28_3_a7,
     author = {P. V. Roldugin},
     title = {Cardinality of subsets of the residue group with nonunit differences of elements},
     journal = {Diskretnaya Matematika},
     pages = {111--125},
     year = {2016},
     volume = {28},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_3_a7/}
}
TY  - JOUR
AU  - P. V. Roldugin
TI  - Cardinality of subsets of the residue group with nonunit differences of elements
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 111
EP  - 125
VL  - 28
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_3_a7/
LA  - ru
ID  - DM_2016_28_3_a7
ER  - 
%0 Journal Article
%A P. V. Roldugin
%T Cardinality of subsets of the residue group with nonunit differences of elements
%J Diskretnaya Matematika
%D 2016
%P 111-125
%V 28
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2016_28_3_a7/
%G ru
%F DM_2016_28_3_a7
P. V. Roldugin. Cardinality of subsets of the residue group with nonunit differences of elements. Diskretnaya Matematika, Tome 28 (2016) no. 3, pp. 111-125. http://geodesic.mathdoc.fr/item/DM_2016_28_3_a7/

[1] Prachar K., Primzahlverteilung, Springer-Verlag, Berlin Gottingen Heidelberg, 1957 ; Prakhar K., Raspredelenie prostykh chisel, Mir, M., 1967, 513 pp. | MR | Zbl | MR

[2] Rosser J., Schoenfeld L., “Approximate formulas for some functions of prime numbers”, Ill. J. Math, 6:1 (1962), 64–94 | MR | Zbl

[3] Stinson D. R. Muir J. A., “On the low Hamming weight discrete logarithm problem for nonadjacent representations”, Appl. Alg. in Eng., Commun. and Comput., 16:6 (2006), 461–472 | DOI | MR | Zbl