Сравнения и их свойства

Говорят, что a сравнимо с b по модулю n, если a-b делится на n. Это обозначают так: a ≡ b (mod n). Сравнения имеют много сходства с равенствами. Если f (x) целая функция с целыми коэффициентами и а ≡ b (mod n), то f (a) ≡ f (b) (mod n).

Решить сравнение f (x) ≡ 0 (mod n) значит найти, какое число надо подставить вместо x для того, чтобы удовлетворить сравнению. Если f (a)делится на n, то данному сравнению удовлетворяют и все числа сравнимые с a по модулю n. Условились, совокупность всех таких чисел называть одним решением данного сравнения. Говорят, что f (x)? ≡ 0 (mod n) имеет m решений, если ему удовлетворяют m чисел несравнимых между собой по модулю п.

Сравнение первой степени ax ≡ b (mod n) возможно, если b делится на d, наибольшего делителя чисел a и b, и имеет d решений. Если n простое число и a не делится на n, то a^{n- 1} ≡ 1 (mod n) ( теоремаФермата ).

Если n простое число, то 1.2.3...(n- 1) ≡ - 1 (mod n) если же n - составное, то 1.2.3...(n- 1)+1 не делится на n (теорема Вильсона).

Сравнение второй степени x² ≡ q (mod p) при простом модуле возможно и имеет два решения, если q ^{(p -1)/2} ≡ 1 (mod p), сравнение невозможно, если q ^{(p -1)/2} ≡ -1 (mod p).

Эти два случая различаются при помощи особого вычисления, предложенного Лежандром и усовершенствованного Якоби. Вычисление выполняется очень быстро даже для больших значений p и q.

Сравнение m -ой степени при простом модуле не может иметь более m решений (теорема Лагранжа).

Функция Эйлера φ(n), где n — натуральное число, равна количеству натуральных чисел, не больших n и взаимно простых с ним. Названа в честь Эйлера, который впервые использовал ее в своих работах по теории чисел

Определение Пусть дано натуральное число , представленное в виде его канонического разложения на простые сомножители

Тогда функция

называется функцией Эйлера. При этом полагается, что (1) = 1.

Функцию Эйлера можно также представить в виде так называемого произведения Эйлера:

где p — простое число и пробегает все значения, участвующие в разложении n на простые сомножители.

Также иногда функцией Эйлера называют функцию от рационального числа :

однако в этой статье о ней речь не идет.

Свойства

1. (pⁿ) = p^{n − 1}(p − 1), если p — простое число. В частности, при n = 1 имеем (p) = p − 1;

2. (mn) = (m) (n), если m и n взаимно просты. То есть Функция Эйлера мультипликативна;

3. , если a и m взаимно просты. Так называемая теорема Эйлера;

4. φ(m^k) = m^{k − 1}φ(m);

5. , если — наименьшее общее кратное, a — наибольший общий делитель.

Функция Мёбиуса μ(n) — мультипликативная арифметическая функция, применяемая в теории чисел и комбинаторике, названа в честь немецкого математика Мёбиуса, который впервые рассмотрел её в 1831г.

Определение. Функция Мёбиуса μ(n) определена для всех положительных натуральных чисел n и принимает значения {-1, 0, 1} в зависимости от характера разложения числа n на простые сомножители:

• μ(n) = 1 если n не делится на квадрат простого числа и разложение n на простые множители состоит из чётного числа сомножителей;
• μ(n) = −1 если n не делится на квадрат простого числа и разложение n на простые множители состоит из нечётного числа сомножителей;
• μ(n) = 0 если n делится на квадрат простого числа.

Принято считать что μ(1) = 1.

Дата добавления: 2015-12-01