Визначення функції Ейлера. Рівняння Ейлера з математики

Функція Ейлера, це функція, яка дорівнює кількості натуральних чисел, менших mі взаємно простих з m. Передбачається, що число 1 взаємно просто з усіма натуральними числами (і з одиниці). Позначається функція Ейлера грецькою буквою φ .

m

Сформулюємо такі завдання.

завдання 1. нехай a 1 , a 2 , a 3, ... все відмінні один від одного прості множники числа m. Знайти число тих чисел, які не діляться ні на одне з чисел a 1 , a 2 , a 3 , ... .

більш спільне завданнямає наступний вигляд:

завдання 2. нехай a 1 , a 2 , a 3, ... взаємно прості числа, які входять множниками в m. Знайти число всіх чисел, які не діляться ні на одне з чисел a 1 , a 2 , a 3 , ... .

Візьмемо ряд натуральних чисел до m:

Їх число дорівнює. Виключимо ці числа з ряду (1). тоді залишаться

Їх кількість дорівнює.

Ці числа можна представити у вигляді ka 2, де kпробігає натуральні числа

.

(3)

Для того щоб ka 2 цієї статті не ділився на a 1 необхідно і достатньо, щоб kНЕ ділився на a 1 (тому що a 1 і a 2 взаємно прості числа). Потрібно знайти кількість чисел з ряду (1), які діляться на a 1 і виключити їх з ряду (3). ділиться на a 1 тому mділиться на a 1 , mділиться на a 2 і mділиться на a 1 a 2 (a 1 , a 2 входять множниками в m m, Яке ми вирішили за допомогою формули (2). з ряду A 1 потрібно виключити числа, які діляться на a 1. Тоді взявши замість mчисло отримаємо

A 2. Далі видалимо з A 2 ті числа, які діляться на a 3. Це ті числа з ряду (1), які діляться на a 3 і не діляться на a 1 і a 2 .

Числа ряду (1), які діляться на a 3 наступні:

Для того щоб ka 3 НЕ ділився на a 1 і a 2 необхідно і достатньо, щоб kНЕ ділився на a 1 і a 2 (тому що a 3 і a 1 а також a 3 і a 2 числа взаємно прості). Потрібно знайти кількість чисел з ряду (1), які діляться на a 1 і a 2 і виключити з ряду (6). ділиться на a 1 і a 2, так як mділиться на a 1 , mділиться на a 2 і mділиться на a 1 a 2 a 3 (a 1 , a 2 , a 3 входять множниками в m). Завдання по відношенню числа та ж, що і завдання по відношенню числа m, Яке ми вирішили за допомогою рівняння (5). Число тих чисел ряду (6), які не діляться ні на a 1 ні на a 2 (або число тих чисел ряду (1), які діляться на a 3 і не діляться ні на a 1, ні на a 2):

Позначимо безліч цих чисел через A 3. Міркуючи таким чином, укладемо, що число A i тих чисел ряду (1), які не діляться на a 1 , a 2 , ..., a i одно

.

(7)

Ми отримали число тих чисел ряду (1), які не діляться на числа a 1 , a 2 , ..., a i. Отримаємо формулу для чисел a 1 , a 2 , ..., a i, a i + 1, де a i + 1 також входить множником в mі взаємно просте з a 1 , a 2 , ..., a i.

Щоб знайти число тих чисел ряду (1), які не діляться на a 1 , a 2 , ..., a i + 1, потрібно з безлічі (7) виключити числа кратні a i + 1. Це ті числа ряду (1), які не діляться на a 1 , a 2 , ..., a i і діляться на a i + 1.

Всі числа ряду (1), які діляться на a i + 1, наступні:

чисел, які не діляться на a 1 , a 2 , ..., a i, тобто

Ми довели наступну теорему:

теорема 1. якщо a 1 , a 2 , ..., a q, все різні взаємно прості числа, що входять до m, То число чисел, які не діляться ні на одне з чисел a 1, a 2 , ..., a q і входять в ряд mодно:

визначається формулою (8).

Дійсно. Будь-яке число, яке не ділиться ні на один з простих множників, що входять до складу mє взаємно простим з m. Тоді враховуючи теорему 1, отримуємо підтвердження цієї теореми.

Знайдена формула можна переписати і в іншому вигляді. Якщо a 1, a 2 , a 3, ... все різні прості числа, що входять множниками в m, то

Таких чисел 24. З огляду на, що 90 = 2 • 3 2 · 5, для φ (m)ми знаходимо

Доведення. якщо a 1 , a 2 , a 3, ... різні прості числа, що входять до складу m 1 і b 1 , b 2 , b 2, ... різні прості числа, що входять до складу m 2, то

різні прості числа, що входять до складу m 1 m 2, так як m 1 і m 2 взаємно прості числа, тобто вони не мають спільних дільників.

Справедливо і зворотне. Будь-яке просте число входить в твір m 1 m 2 має збігатися з числом з ряду (9), так як це просте число входить множником або в m 1, або в m 2 .

Таким чином числа ряду (9) представляють безліч всіх простих чисел, що входять у твір m 1 m 2. отже

З іншого боку

Ця теорема справедлива і для будь-якого числа співмножників, якщо ці співмножники взаємно прості числа.

Дійсно.

чисел взаємно простих з m.

Більш спільне завдання полягає в наступному:

завдання 3. Дан ряд (10) і потрібно знайти число тих чисел, цього ряду, які мають з mнайбільший спільний дільник λ , причому m = nλ, Тобто λ є одним з дільників числа m.

Очевидно, що шукані числа знаходяться серед чисел

Для того щоб λ було найбільшим загальним дільником чисел m = nλі kλз ряду (11), необхідно і достатньо, щоб kі nбули числами взаємно простими. Отже, тому що kприймає значення

і розіб'ємо ряд

Розглянемо приклад.

приклад. нехай m= 90. подільники числа mнаступні:

Дзета-функція Рімана - одна з найвідоміших формул чистої математики, з якою пов'язана знаменита невирішена математична проблема - гіпотеза Рімана. Калькулятор дзета-функції дозволяє обчислити її значення для аргументів, що лежать в межах від нуля до 1.

Історична довідка

Історія дзета-функції Рімана починається з гармонійного ряду, відкритого ще піфагорійцями, який виглядає як:

1 + 1/2 + 1/3 + 1/4 + 1/5 ... 1 / n

Ряд отримав свою назву завдяки утвердженню, що струна, розділена надвоє, натроє або більше, видає звуки, що радять математичної гармонії. Чим більша кількість членів гармонійного ряду, тим більше його значення. Говорячи строгим математичним мовою, це означає, що ряд розходиться і прямує до нескінченності.

Відомий математик Леонард Ейлер працював з гармонійним рядом і вивів формулу для визначення суми заданого кількості членів послідовності. У процесі роботи він зацікавився іншим поруч, який був відомий з давніх часів, однак сьогодні носить ім'я Ейлера. Дробу ейлерового ряду в знаменниках містять квадрати, а перші члени послідовності виглядають так:

1 + 1/4 + 1/9 + 1/16 + 1/25 ... 1 / n 2

Дивно, однак, при збільшенні кількості членів ряду, сума вираження асимптотично наближається до певного значення. Отже, ряд сходиться, а його значення прагне до константі, яка дорівнює (Pi 2) / 6 або 1,64488. Якщо в знаменники поставити куби:

1 + 1/8 + 1/27 + 1/64 + 1/125 ... 1 / n 3

то ряд знову сходиться, але вже до значення 1,20205. В Загалом виглядіми можемо уявити статечної ряд як дзета-функцію виду:

Z (s) = 1 + 1/2 s + 1/3 s + 1/4 s + 1/5 s

Зі збільшенням ступеня і кількості членів ряду значення функції буде прагнути до одиниці і для ступенів вище 30 вираз Z (s) = 1, отже, такий ряд сходиться. Обчислення значення ряду при 0> s> 1 показує, що у всіх цих випадках функція має різні значення, а сума членів ряду при прагненні до нескінченності постійно збільшується, відповідно, ряд розходиться.

У гармонійному ряду показник ступеня дорівнює одиниці і ряд також розходиться. Однак як тільки s приймає значення більше одиниці, то ряд сходиться. Якщо ж менше - то розходиться. З цього випливає, що гармонійний ряд знаходиться строго на кордоні збіжності.

Дзета-функція Рімана

Ейлер працював з цілими ступенями, однак Бернхард Ріман розширив своє розуміння функції на дійсні і комплексні числа. Комплексний аналіз показує, що дзета-функція має нескінченну кількість нулів, тобто нескінченну кількість значень s, при яких Z (s) = 0. Усі нетривіальні нулі являють собою комплексні числа виду a + bi, де i - уявна одиниця. Наш онлайн-калькулятор дозволяє оперувати тільки з дійсними аргументами, тому значення Z (s) завжди буде більше нуля.

Наприклад, Z (2) = (Pi 2) / 6, і цей результат розрахував сам Ейлер. Всі значення функції для парних аргументів містять число Пі, проте розрахунок для непарних чисел занадто складний для представлення результату в замкнутому вигляді.

гіпотеза Рімана

Леонард Ейлер використовував функцію Z (s) при роботі з теоремою про розподіл простих чисел. Ріман також ввів цю функцію в своїй дисертаційній роботі. Праця містив метод, що дозволяє підрахувати кількість простих чисел (діляться тільки на себе і на одиницю), які зустрічаються в ряду до певної межі. По ходу роботи Ріман зробив зауваження, що все нетривіальні (тобто, комплексні) нулі дзета-функції мають дійсну частину, рівну 1/2. Вчений так і не зміг вивести суворе доказ цього твердження, яке з часом перетворилося в Священний Грааль чистої математики.

Суворе доказ гіпотези Рімана обіцяє пролити світло на розподіл простих чисел, над яким математичне співтовариство б'ється з античних часів. На сьогоднішній день розраховане понад півтора мільярда нетривіальних нулів дзета-функції, і вони дійсно розташовуються на лінії x = 1/2. Однак, ні теорія про розподіл неподільних чисел, ні гіпотеза Рімана на даний момент не дозволені.

Наш калькулятор дозволяє розраховувати значення Z (s) для будь-яких дійсних s. Ви можете використовувати цілі і дробові, позитивні і негативні значення аргументу. При цьому цілі позитивні s завжди будуть давати результат близький або дорівнює одиниці. Значення 0> s> 1 завжди призводять до того, що дзета-функція приймає різні значення. Негативні значення s звертають ряд в:

1 + 1 s + 2 s + 3 s + 4 s ...

Очевидно, що при будь-якому негативному s ряд розходиться і різко спрямовується в нескінченність. Розглянемо чисельні приклади значення Z (s).

приклади обчислень

Давайте перевіримо наші викладки. В обчисленнях програма використовує 20 тисяч членів ряду. Визначимо за допомогою калькулятора значення Z (s) для позитивних аргументів більше одиниці:

• при s = 1 вираз Z (s) = 10,48;
• при s = 1,5 вираз Z (s) = 2,59;
• при s = 5 вираз Z (s) = 1,03.

Розрахуємо значення дзета-функції для 0> s> 1:

• при s = 0,9 вираз Z (s) = 17,49.
• при s = 0,5 вираз Z (s) = 281,37;
• при s = 0,1 вираз Z (s) = 8 253,59.

Розрахуємо значення Z (s) для s<0:

• при s = -0,5 вираз Z (s) = 1 885 547.
• при s = -1 вираз Z (s) = 199 999 000;
• при s = -3 вираз Z (s) = 39 996 000 100 000 010;

Очевидно, що при невеликій зміні s від одиниці в більшу сторону функція починає повільне, але неухильне рух до Z (s) = 1. При зміні аргументу від одиниці в меншу сторону функція приймає всі великі і великі значення і спрямовується в нескінченність.

висновок

Дзета-функція Рімана і пов'язана з нею гіпотеза - одна з найбільш популярних відкритих проблем сучасної математики, над вирішенням якої вчені б'ються вже більше 150 років. Доказ гіпотези Рімана дозволить математикам зробити великий прорив в теорії чисел, що, безсумнівно, призведе наукове співтовариство до ще більших відкриттів.

Умова

У теорії чисел відома функція Ейлера$ Latex \ varphi (n) $ - кількість чисел, менших $ latex n $ і взаємно простих з ним. Нагадаємо, два числа взаємно прості, якщо у них немає спільних дільників, крім одиниці.

Розширимо поняття функції Ейлера на рядки. Нехай $ latex s $ - непорожній рядок над алфавітом ($ latex a $ .. $ latex z $), а $ latex k $ - ціле позитивне число. Тоді $ latex s \ cdot k $ за визначенням - рядок $ latex t = \ underbrace (s \ circ s \ circ \ ldots \ circ s) _ (\ text (k)) $ (конкатенація $ latex s $ самої з собою $ latex k $ раз). В такому випадку будемо говорити, що рядок $ latex s $ - дільникрядки $ latex t $. Наприклад, «ab» - дільник рядки «ababab».

Дві непусті рядка $ latex s $ і $ latex t $ називатимемо взаємно простими,якщо не існує рядка $ latex u $ такий, що вона - дільник і для $ latex s $, і для $ latex t $. Тоді функція Ейлера $ latex \ varphi (s) $ для рядка $ latex s $ за визначенням - кількість непустих рядків над тим же алфавітом ($ latex a $ .. $ latex z $), менших $ latex s $ по довжині, і взаємно простих з нею.

Вхідні дані

У вхідному файлі дана рядок $ latex s $ довжиною від $ latex 1 $ до $ latex 10 ^ 5 $ символів включно, що складається з маленьких латинських літер.

Вихідні дані

Розрахуйте значення $ latex \ varphi (s) $ і виведіть єдине число - залишок від його поділу на $ latex 1000000007 (10 ^ 9 + 7) $.

Рішення

Очевидно, що коли рядок $ latex s $ довжини $ latex n $ не має дільників, крім самої себе, будь-який рядок довжини меншою, ніж $ latex n $, буде взаємно простий з $ latex s $. Тоді досить порахувати кількість всіх можливих рядків довжини від $ latex 1 $ до $ latex n-1 $ включно. Для деякого $ latex k $ кількість рядків цієї довжини дорівнюватиме $ latex 26 ^ k $. Тоді кількість $ latex m $ всіх можливих рядків довжини від $ latex 1 $ до $ latex n-1 $ буде обчислюватися за такою формулою: $ latex m = \ sum \ limits_ (k = 1) ^ (n-1) 26 ^ k $.

Тепер розглянемо випадок, коли рядок має подільники. Оскільки рядок $ latex s $ в такому випадку є конкатенацией деякої кількості однакових рядків меншої довжини, знайдемо цю саму подстроку, кторая є мінімальним (найкоротшим) делителем рядка $ latex s $. Для цього скористаємося префікс-функцією. Вона повертає вектор $ latex pi $ значень для всіх подстрок рядка $ latex s $, які є префіксами $ latex s $, де значення - максимальна довжина префікса рядки, що збігається з її суфіксом. Тоді на $ latex n-1 $ -му місці вектора $ latex pi $ стоятиме довжина найбільшого префікса рядка $ latex s $, а залишився «шматочок» рядки $ latex s $ представлятиме собою мінімальний дільник.

Залишилося обчислити кількість рядків, що не взаємно прості з $ latex s $. Нехай k - довжина мінімального подільника $ latex s $. Тоді всі рядки, є конкатенації цього подільника, що не будуть взаємно простими з $ latex s $. Для підрахунку їх кількості достатньо поділити довжину початкового рядка на k, але відповідь буде на одиницю менше, оскільки в цій формулі враховується і сама рядок $ latex s $, як власний дільник.

Для остаточної відповіді на завдання залишається відняти від загальної кількості рядків кількість не взаємно простих з $ latex s $.

тести

Програмний код

І значення її лежать в безлічі натуральних чисел.

Як випливає з визначення, щоб обчислити потрібно перебрати всі числа від до і для кожного перевірити, чи має воно загальні дільники з а потім підрахувати, скільки чисел виявилися взаємно простими з Ця процедура дуже трудомістка, тому для обчислення використовують інші методи, які ґрунтуються на специфічних властивості функції Ейлера.

У таблиці праворуч представлені перші 99 значень функції Ейлера. Аналізуючи ці дані, можна помітити, що значення не перевищує, і в точності йому одно, якщо - просте. Таким чином, якщо в координатах провести пряму то значення будуть лежати або на цій прямій, або нижче її. Також, дивлячись на графік, наведений на початку статті, і на значення в таблиці, можна припустити, що існує пряма, яка проходить через нуль, яка обмежує значення знизу. Однак, виявляється, такий прямий не існує. Тобто, яку б пологу пряму ми ні провели, завжди знайдеться натуральне число таке що лежить нижче цієї прямої. ще однією цікавою особливістюграфіка, є наявність деяких прямих, уздовж яких концентруються значення функції Ейлера. Так, наприклад, крім прямої на якій лежать значення де - просте, виділяється пряма, приблизно відповідна на яку потрапляють значення де - просте.

Більш докладно поведінку функції Ейлера розглядається в розділі.

Мультипликативность функції Ейлера

Одним з основних властивостей функції Ейлера є її мультипликативность. Це властивість було встановлено ще Ейлером і формулюється воно в такий спосіб: для будь-яких взаємно простих чиселі

доказ мультипликативности

Для доказу мультипликативности функції Ейлера буде потрібно наступна допоміжна теорема.

Тепер можна довести основне твердження.

Функція Ейлера від простого числа

яка випливає з визначення. Дійсно, якщо - просте, то все числа, менші, взаємно прості з ним, а їх рівно штук.

Для обчислення функції Ейлера від ступеня простого числа використовують наступну формулу:

Це рівність обґрунтовується наступним чином. Підрахуємо кількість чисел від до, що не взаємно прості с. Всі вони, очевидно, кратні тобто, мають вигляд: Всього таких чисел Тому кількість чисел, взаємно простих з одно

Функція Ейлера від натурального числа

Обчислення для довільного натурального грунтується на мультипликативности функції Ейлера, вираженні для а також на з основною теоремою арифметики. Для довільного натурального числа значення представляється у вигляді:

де - просте числоі пробігає всі значення, які беруть участь в розкладанні на прості множники.

Доведення

де - найбільший спільний дільникі Ця властивість є природним узагальненням мультипликативности.

Доказ узагальненої мультипликативности

Нехай тоді причому в загальному випадку і Тому можна записати:

Тут перші дільників є також делителями а останні дільників є дільниками Розпишемо:

В силу мультипликативности функції Ейлера, а також з урахуванням формули

де - просте, отримуємо:

У першому рядку записано в другій - а третю можна уявити, як Тому:

Деякі окремі випадки:

теорема Ейлера

Найбільш часто на практиці використовується властивість, встановлене Ейлером :

якщо і взаємно прості.
Це властивість, яке називають теоремою Ейлера, Випливає з теореми Лагранжаі того факту, що φ ( m) Дорівнює порядку групи оборотних елементів кільця відрахуваньпо модулю m.
Як слідства теореми Ейлера можна отримати малу теорему Ферма. Для цього потрібно взяти не довільне а просте. тоді:

Остання формула знаходить застосування в різних тестах простоти.

інші властивості

Виходячи з представимости твором Ейлера, нескладно отримати наступне корисне твердження:

Будь-яке натуральне число можна подати у вигляді суми значень функції Ейлера від його подільників:

Сума всіх чисел, менших даного, і взаємно простих з ним, виражається через функцію Ейлера:

безліч значень

Дослідження структури множини значень функції Ейлера є окремою складним завданням. Тут представлені лише деякі результати, отримані в цій області.

Доказ (функція Ейлера приймає лише парні значення при n> 2)

Дійсно, якщо - просте непарне і то - парне. З рівності випливає твердження.

У дійсному аналізі часто виникає задача знаходження значення аргументу по заданому значенню функції, або, іншими словами, завдання знаходження зворотної функції. Таке завдання можна поставити і для функції Ейлера. Однак, треба мати на увазі, що

У зв'язку з цим потрібні особливі методи аналізу. Корисним інструментом для дослідження прообразу є наступна теорема:

доказ теореми

Очевидно, якщо то З іншого боку, якщо і те Однак, якщо то Тому Отже

Ця теорема показує, що прообраз елемента завжди є кінцеве безліч. Також вона дає практичний спосіб знаходження прообразу. Для цього потрібно

Може виявитися, що в зазначеному проміжку немає такого числа що в цьому випадку прообраз є порожнім безліччю.
Варто зазначити, що для обчислення потрібно знати розкладанняна прості множники, що для великих є обчислювально складноїзавданням. Потім, потрібно раз обчислити функцію Ейлера, що для великих чисел також вельми трудомістким. Тому знаходження прообразу в цілому є обчислювально складним завданням.

Приклад 1 (Обчислення прообразу)

Знайдемо прообраз 4. дільник 4 є числа 1, 2 і 4. Додаючи по одиниці до кожного з них, отримуємо 2, 3, 5 - прості числа. обчислюємо

Щоб знайти прообраз 4, досить розглянути числа від 5 до 15. Проробивши викладки, отримаємо:

Приклад 2 (Не всі парні числа є значеннями функції Ейлера)

Не існує, наприклад, такого числа що Тобто:

Справді, подільники 14 суть 1, 2, 7 і 14. Додавши по одиниці, отримаємо 2, 3, 8, 15. З них тільки перші два числа - прості. Тому

Перебравши всі числа від 15 до 42, нескладно переконатися, що

асимптотичні співвідношення

найпростіші нерівності

Порівняння φ ( n) з n

Ставлення послідовних значень

Асимптотики для сум

Порядок функції Ейлера

Зв'язок з іншими функціями

функція Мебіуса

ряд Діріхле

ряд Ламберта

Найбільший спільний дільник

Додатки та приклади

Функція Ейлера в RSA

На основі алгоритму, запропонованого в 1978 році Рональдом Ривестом , Аді Шамірі Леонардом Адлеманомбула побудована перша система шифрування з відкритим ключем, що отримала назву за першими літерами прізвищ авторів - система RSA. Крипостійкість цієї системи визначається складністю розкладання на множникицілого n-розрядним числа. Ключову роль в алгоритмі RSA грає функція Ейлера, властивості якої і дозволяють побудувати криптографічний систему з відкритим ключем.

На етапі створення пари з секретного і відкритого ключів, обчислюється

де і - прості. Потім вибираються випадкові числа так, щоб

Потім повідомлення шифрується відкритим ключем адресата:

Після цього розшифрувати повідомлення може тільки власник секретного ключа

Коректність останнього твердження ґрунтується на теоремі Ейлераі китайської теореми про залишки.

Доведення коректності розшифрування

В силу вибору чисел на етапі створення ключів

Якщо те, з урахуванням теореми Ейлера,

У загальному випадку і можуть мати спільні дільники, але розшифрування все одно виявляється вірним. Нехай За китайською теоремі про залишки:

Підставляючи отримуємо тотожність

отже,

Обчислення зворотного елемента

Функція Ейлера може бути використана для обчислення зворотного по множенню елемента по модулю, а саме:

Приклад (Обчислення зворотного елемента)

Знайдемо, тобто таке число, що

Очевидно, і не мають спільних дільників крім одиниці,, при цьому число просте і

тому зручно скористатися формулою, наведеною вище:

Легко перевірити, що справді

Зауваження 1 (Оцінка складності обчислення)

У загальному випадку для обчислення зворотних значень алгоритм Евклідашвидше, ніж використання теореми Ейлера, так як бітова складність обчисленняза алгоритмом Евкліда має порядок в той час як обчислення по теоремі Ейлера вимагає порядку бітових операцій, де Однак, в разі, коли відомо розкладання на прості множники, складність обчислень можна зменшити, використовуючи алгоритми швидкого зведення в ступінь: алгоритм Монтгомеріабо алгоритм "Зводь в квадрат і перемножуємо".

Зауваження 2 (Відсутність рішення в разі (a, n) ≠ 1)

Якщо то зворотного до елемента не існує, або, інакше кажучи, рівняння

не має рішення на множині натуральних чисел.
Доведення.Справді, припустимо

і рішення існує. Тоді за визначенням найбільшого загального дільника

тому можна записати:

або, перегрупувавши складові,

Зліва стоїть ціле відмінне від нуля число, значить і справа має бути ціле відмінне від нуля число, тому з необхідністю

що суперечить припущенню.

Рішення лінійного порівняння

Метод обчислення зворотного елемента можна використовувати для вирішення порівняння

Приклад (Рішення лінійного порівняння)

Розглянемо порівняння

Так як можна скористатися зазначеної формулою:

Підстановкою переконуємося, що

Зауваження (неєдиним рішення або відсутність рішення в разі (a, n) ≠ 1)

Якщо, порівняння або має не єдине рішення, або не має рішення. Як легко переконатися, порівняння

не має рішення на множині натуральних чисел. У той же час порівняння

має два рішення

Обчислення залишку від ділення

Функції Ейлера дозволяє обчислювати залишки від ділення великих чисел.

Приклад 1 (Останні три цифри в десяткового запису числа)

Знайдемо останні три цифри в десяткового запису числа Помічаючи, що

отримуємо

Переходячи тепер від модуля до модуля маємо:

Отже, десяткова запис числа закінчується на

Приклад 2 (Залишок від ділення на 1001)

Знайдемо залишок від ділення на Легко бачити, що

Тому, скориставшись мультиплікативний функції Ейлера і рівністю

отримуємо

Знаходження порядку мультипликативной групи кільця відрахувань

Мультиплікативна група кільця відрахуваньпо модулю складається з класів відрахувань.
Приклад.Наведена система відрахувань по модулю 14 складається з класів відрахувань:

Додатки в теорії груп

число породжують елементівв кінцевої циклічноїгрупі одно. Зокрема, якщо мультипликативная група кільця відрахуваньпо модулю є циклічною групою - що можливо тільки при, де - просте непарне, - натуральне, - то існує генераторів групи ( первісних коренівпо модулю).
Приклад.Група розглянута в прикладі вище, має генератора: і

невирішені питання

завдання Лемера

Як відомо, якщо - просте, то 1932-го Лемер ( англ.) Задався питанням, чи існує таке складене число що є дільником Лемер розглядав рівняння

де - ціле. Йому вдалося довести, що якщо - рішення рівняння, то або - просте, або воно є твором семи або більше різних простих чисел. Пізніше були доведені і інші сильні затвердження. Так в 1980 році Cohen і Hagis показали, що якщо складене і ділить то і де - кількість простих дільників. У 1970 році Lieuwens встановив, що якщо то і Wall в 1980 році довів, що якщо то