О соотношениях, связанных с функцией Эйлера

О соотношениях, связанных с функцией Эйлера

Леонтьев В. К., Гордеев Э. Н.
Дискретный анализ и исследование операций, 30, 4, 35–45 (2023)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2023.30.775

Аннотация:

Исследуются свойства множества чисел, меньших и взаимно простых c $n$, с введённой на нём операцией умножения по модулю $n$ (этот объект иногда называют группой Эйлера). Мощность такого множества — известная функция Эйлера $\varphi(n)$, которая является одной из классических функций теории чисел. Области её применения достаточно широкие и включают, например, различные разделы дискретной математики, а также имеют существенные приложения в криптографии. В работе рассматриваются различные комбинаторные задачи, возникающие при исследовании группы Эйлера и функции Эйлера. Выведены соотношения между теоретико-числовыми параметрами, связанными с группой Эйлера и функцией Эйлера. Полученные в работе комбинаторные соотношения могут быть использованы при решении прикладных комбинаторных проблем и в криптографии. 
Библиогр. 10.

Литература:
  1. Арнольд В. И. Группы Эйлера и арифметика геометрических прогрессий. М.: МЦНМО, 2003. 44 с.
     
  2. Сачков В. Н. Введение в комбинаторные методы дискретной математики. М.: МЦНМО, 2004.
     
  3. Алфёров А. П., Зубов А. Ю., Кузьмин А. С., Черёмушкин А. В. Основы криптографии. М.: Гелиос АРВ, 2002. 480 с.
     
  4. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998.
     
  5. Hardy G. H., Wright E. M. An introduction to the theory of numbers. Oxford: Clarendon Press, 1979. 426 p.
     
  6. Shramm W. The Fourier transform of functions of the greatest common divisor // INTEGERS: Electron. J. Comb. Number Theory. 2008. V. 8. Paper ID A50. 7 p.
     
  7. Coleman R. Some remarks on Euler’s totient function. Ithaca, NY: Cornell Univ., 2012. (Cornell Univ. Libr. e-Print Archive; arXiv:1207.4446).
     
  8. Леонтьев В. К. Комбинаторика и информация. Ч. 1. Комбинаторный анализ. М.: МФТИ, 2015. 174 с.
     
  9. Бейтмен Г., Эрдейи А. Высшие трансцендентные функции. Т. 3. М.: Наука, 1967. 296 с.
     
  10. Курош А. Г. Курс высшей алгебры. М.: Наука, 1968. 431 с.
Леонтьев Владимир Константинович
  1. Вычислительный центр им. А. А. Дородницына ФИЦ ИУ РАН, 
    ул. Вавилова, 40, 119333 Москва, Россия

E-mail: vkleontiev@yandex.ru

Гордеев Эдуард Николаевич
  1. Вычислительный центр им. А. А. Дородницына ФИЦ ИУ РАН, 
    ул. Вавилова, 40, 119333 Москва, Россия

E-mail: werhorn@yandex.ru

Статья поступила 23 мая 2023 г. 
После доработки — 2 августа 2023 г. 
Принята к публикации 20 августа 2023 г.

Abstract:

The paper studies the properties of the set of numbers smaller than and coprime to $n$ with the modulo $n$ multiplication operation introduced on it (this object is sometimes called the Euler group). The cardinality of such a set is the well-known Euler function $\varphi(n)$, which is one of the classical functions in the number theory. The fields of its application are quite wide and include, for example, various branches of discrete mathematics, and it also has significant applications in cryptography. The paper considers various combinatorial problems arising in the study of the Euler group and the Euler function. Relations between theoretical and numerical parameters associated with the Euler group and Euler function are derived. The combinatorial relations obtained in the paper can be used when solving applied combinatorial problems and in cryptography. 
Bibliogr. 10.

References:
  1. V. I. Arnold, Euler Groups and Arithmetics of Geometric Progression (MTsNMO, Moscow, 2003) [Russian].
     
  2. V. N. Sachkov, An Introduction to Combinatorial Methods of Discrete Mathematics (MTsNMO, Moscow, 2004) [Russian].
     
  3. A. P. Alfyorov, A. Yu. Zubov, A. S. Kuzmin, and A. V. Cheryomushkin, Basics of Cryptography (Gelios ARV, Moscow, 2002) [Russian].
     
  4. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science (Addison-Wesley, Reading, MA, 1994; Mir, Moscow, 1998 [Russian]).
     
  5. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers (Clarendon Press, Oxford, 1979).
     
  6. W. Shramm, The Fourier transform of functions of the greatest common divisor, INTEGERS: Electron. J. Comb. Number Theory 8, Paper ID A50 (2008).
     
  7. R. Coleman, Some remarks on Euler’s totient function (Cornell Univ., Ithaca, NY, 2012) (Cornell Univ. Libr. e-Print Archive, arXiv:1207.4446).
     
  8. V. K. Leontiev, Combinatorics and Information. Pt. 1. Combinatorial Analysis (Mosk. Fiz. Tekh. Inst., Moscow, 2015) [Russian].
     
  9. H. Bateman and A. Erdélyi, Higher Transcendental Functions, Vol. 3 (New York, McGraw-Hill Book Co., 1953; Nauka, Moscow, 1967 [Russian]).
     
  10. A. G. Kurosh, A Course in Higher Algebra (Nauka, Moscow, 1968) [Russian].