Программа государственного экзамена по математике для студентов математического факультета Московского городского педагогического университета — страница 5

  • Просмотров 2574
  • Скачиваний 217
  • Размер файла 88
    Кб

мультипликативны. Тогда, обозначив через h произведение функций f и g, имеем: h(xy)=f(xy)g(xy)=f(x)f(y)g(x)g(y)=[f(x)g(x)][f(y)g(y)]= =h(x)h(y). Следствие. Для любого целого k функция q(x)= xk вполне мультипликативна. 20. Сумма значений функции по всем делителям аргумента. Введем в рассмотрение, наряду с функцией q(x), функцию , равную сумме всех значений функции q(d) при условии, что переменная d пробегает все делители числа x. Теорема (основное тождество). Если x=, то ×.

В частности, если функция q вполне мультипликативна, то и функция также вполне мультипликативна. Доказательство. Рассмотрим произведение сумм, находящееся в правой части требуемого равенства: = = Осталось заметить, что для каждого набора (g1, g2,..., gk ) целых неотрицательных чисел gi, не превосходящих ai, в сумме каждое слагаемое встречается ровно один раз. Учитывая теперь, что каждый делитель числа имеет вид , получаем . Свойство полной

мультипликативности рассматриваемой функции немедленно вытекает из того, что взаимно простые числа содержат различные простые сомножители. ÿ 30. Число делителей t(x) и сумма делителей s(x). Рассмотрим следующие вполне мультипликативные функции: t(x)= , где q(x)=1, - число делителей числа x, s(x)= , где q(x) = x, - сумма делителей числа x. Теорема. Справедливы тождества: t()=(a1 + 1)( a2 + 1)...( ak + 1), s()= Доказательство. а) Из определения функции t(x)

немедленно следует указанное тождество, поскольку в силу основного тождества легко подсчитать число слагаемых, каждое из которых равно 1, в каждой из скобок соответствующего произведения. б) Это тождество получается из основного тождества и формулы суммы членов геометрической прогрессии: ÿ 40. Функция Эйлера. Одной из важнейших числовых функций является следующая функция, впервые введенная в рассмотрение Эйлером.

Определение. Через j(x) обозначается количество чисел ряда 1, 2, ..., x, (*) взаимно простых с числом x. Справедлива следующая теорема, которую приведем без доказательства. Теорема. Если x=, то j(x)= x× Следствие. Функция Эйлера вполне мультипликативна и Теорема (тождество Гаусса). . Доказательство. Применяя основное тождество и последнее следствие, получаем, считая , ÿ 4. Алгоритм Евклида и его применения 10. Алгоритм Евклида. Наибольший

общий делитель чисел a, b можно найти с помощью алгоритма Евклида, который состоит в следующем. Пусть b>0. Разделим a на b, тогда по теореме о делении с остатком: a = bq1 + r1. Если r1 = 0, то НОД(a, b) = b. Если r1 ¹ 0, то разделим b с остатком на r1: b = r1q2 + r2. Если r2 = 0, то процесс деления закончим, а если r2 ¹ 0, то разделим r1 с остатком на r2 : r1 = r2q3 + r3. Продолжая далее таким же образом, мы закончим процесс деления как только получится остаток равный 0.