Материал: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi

Скачать файл

Заказать новую работу

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

Розв’язання

У числі

n! множників, які кратні

p ,

буде

. Серед них

кратних p 2 ,

доки pk £ n ,

множників,

буде

і т.

д. доти,

а pk +1 > n . Отже, загальна кількість входжень p до n! буде

a =

+ ... +

Приклад

Знайти з яким степенем число p = 2 входить до числа 11!

Розв’язання

a =	11	+	11	+	11	= 5 + 2 +1 = 8 .

2		4		8

Дійсно, 11! = 1× 2 ×3× 4 ×5 ×6 ×7 ×8 ×9 ×10 ×11 =

= 1× 21 ×3× 22 ×5 ×(21 ×3)×7 × 23 ×9 ×(21 ×5)×11 .

Порахувавши усі степені 2, побачимо, що 2 входить у число 11! дійсно у степені 1 + 2 +1 + 3 +1 = 8 .

2.2. МУЛЬТИПЛІКАТИВНІ ФУНКЦІЇ

Функція f (a) називається мультиплікативною, якщо для неї виконуються 2 умови:

1. f (a) визначена для усіх a = 0,1,2... і хоча б для одного a0 f (a0 ) = 0 ;

2. Для будь-яких a1 , a2 : (a1 , a2 ) = 1 виконується таке: f (a1 × a2 ) = f (a1 )× f (a2 )

Приклад -

a r , де r R .

Властивості мультиплікативних функцій

1. Для будь-якої мультиплікативної функції

f (1) = 1 .

Якщо розглянути a1 , a2 ,..., ak попарно простих чисел, то

f (a1 × a2 ×... × ak ) =

f (a1 )× f (a2 )×... × f (ak ), зокрема

f (p

α1

α2 ×... × p

αk )=

(p α1 )× f (p

α2 )×... × f (p

αk ).

Наприклад,

задамо

мультиплікативну

функцію

так:

f (1) = 1,

f (pα )= 2,

"a > 0 .

Тоді

для

довільного цілого

числа

a = p α1

× p

α2

×...× p

αk

> 0,

i =

будемо мати

1, k

f (p

α1

× p

α2 ×...× p

αk

f (p

α1 )× f (p

α2 )×...× а(p

αk )= 2k ,

зокрема

f (1) = 1, f (2) = 2, f (7) = 2,

f (9) = f (32 ) = 2,

f(14) = f (2 ×7) = f (2) f (7) = 4.

2.Добуток двох мультиплікативних функцій – функція мультиплікативна.

Нехай f (a) = f1 (a) f2 (a) – задана функція.

f(a1 × a2 ) = f1 (a1 × a2 ) f2 (a1 ×a2 ) = f1 (a1 ) f1 (a2 ) f2 (a1 ) f2 (a2 ) =

=( f1 (a1 ) f2 (a1 ))( f1 (a2 ) f2 (a2 )) = f (a1 ) f (a2 ) .


3. Нехай a = p1α1 × p2		α2	× ...× pk αk - довільне ціле число,				f (a) -
довільна мультиплікативна				функція, D \| a -	множина		усіх
дільників a виду d = p1	β1		× p2	β2 × ...× pk βk , 0 £ βi	£ α i , i =			.
						1,k
Тоді вірним буде таке:

∑ f (d ) = (1+ f ( p1 ) + f ( p12 ) + ... + f ( p1α1 ))´

D|a

´(1+ f ( p2 ) + f ( p22 ) + ... + f ( p2α2 ))´...

´(1+ f ( pk ) + f ( pk 2 ) + ... + f ( pk αk )) .

2.3.ПРИКЛАДИ МУЛЬТИПЛІКАТИВНИХ ФУНКЦІЙ

1.Кількість дільників числа a = p1α1 × p2 α2 ×...× pk αk .

Введемо мультиплікативну			функцію	f (a) =1 . Розглянемо
для цієї функції 3-ю властивість мультиплікативних функцій.
Ліва	частина: ∑ f (d ) = ∑1 = 1 +1 +1... становить				кількість
	D\|a	D\|a
дільників числа a . Права частина: (1 + a1 )(1 + a2 )...(1+ ak ).
Отже,	кількість	дільників	числа a	дорівнює	добутку

степенів усіх простих чисел, що входять до канонічного розкладання числа, збільшених на 1. Позначимо функцію визначення кількості дільників числа, як t(a) . Тоді можна записати

t(a) = (1 + a1 )(1 + a2 )...(1 + ak ).

t(a) – мультиплікативна функція визначення кількості дільників числа a = pα , α > 0 , дорівнює

τ (pα )= (α + 1) .

Для p простого числа кількість дільників дорівнює

τ ( p) = 1 +1 = 2 .

Приклад

Знайти кількість дільників числа:

1. a = 31; 2. a = 64 = 26 ; 3. a = 84 = 22 ×3 × 7 .

Розв’язання

1.	a = 31 – просте число. Отже, τ (31) = 1 +1 = 2 . Це числа 1
і 31.	a = 64 = 26 – степінь простого числа 2. Отже,
2.	a = 64 = 26 – степінь простого числа 2. Отже,

τ (26 ) = 6 +1 = 7 .

3. a = 84 = 2	2 ×3 × 7 – число типу a = p α1	× p	α2	×...× p	αk ,
	1		2		k

τ (22 ×3× 7) = τ (22 )×τ (3)×τ (7) = (2 +1)(1 +1)(1 +1) = 3× 2 × 2 = 12 .

2. Сума додатних дільників числа a = p1α1 × p2 α2 ×...× pk αk .

Введемо мультиплікативну функцію f (a) = a і підставимо її

увластивість 3. Отримаємо:

∑d = (1+ p1 + p12 + ... + p1α1 )×

D|a

´(1+ p2 + p22 + ... + p2α2 ) ×...×(1+ pk + pk 2 + ... + pk αk ) .

Ліворуч у формулі стоїть сума усіх додатних дільників числа a . Позначимо цю суму S (a) . Праворуч у дужках маємо суми геометричних прогресій із знаменниками p1 , p2 ,..., pk .

Використовуючи формулу суми геометричної прогресії для

n = ai +1,

(i =

) членів, отримаємо

1, k

S (p α1

× p

α2 ×...× p

αk )=

p1α1 +1 -1

α2 +1 -1

×...×

pk αk +1 -1

p1 -1

p2 -1

pk -1

S (a)

–

мультиплікативна

функція

визначення суми

додатних дільників числа a = pα , α > 0 дорівнює:

S (pα )= pα+1 -1 . p -1

Приклад

Знайти суму дільників числа:

1. a = 24 ×5 ×73 ×19 ; 2. a = 84 = 22 ×3 × 7 .

Розв’язання

1. S (24 ×5 ×73 ×19)= 25 -1 × 52 -1 × 74 -1 ×192 -1 = 1488000 ;

2. S (22 ×3 × 7)= 23 -1 × 32 -1 × 72 -1 = 5 ×8 × 48 = 160 . 1 2 6 12

3. Функція Ейлера та її властивості

Означення

Функція Ейлера визначає для довільного цілого додатного числа a кількість чисел з ряду цілих 0 £ bi £ a -1, взаємно

простих з числом a , тобто таких, що (a,bi ) = 1. Позначається функція Ейлера j(a).

Приклади j(1) =1 - за означенням.

a = 2, j(2) =1 , поперед числа 2 є одне число – 1; a = 3, j(3) = 2 , взаємно прості з 3 – 1,2;

a = 4, j(4) = 2 , взаємно прості з 4 – 1,3;

a = 5, ϕ(5) = 4 ,	взаємно прості з 5 – 1,2,3,4;
a =13, j(13) =12	, оскільки 13 – просте число, то увесь ряд

цілих чисел, менших за 13 є взаємно простий з ним.

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

степенем простого числа:

1) для a = p –

простого числа – j(p) = p1 - p0 = p -1 ;

2) для a = pα

–

степеня простого числа –

j(p) = pα 1

= pα - p

α−1 .

Функція Ейлера є мультиплікативною функцією.

Розглянемо

канонічне

подання

довільного

цілого

a = p α1

× p

α2 ×...× p

αk

. Для довільного

цілого

функція

Ейлера

буде мати вигляд

α1

α2

αk

j(a) = j(p1

× p2

×... × pk

)= a × 1 -

1 -

... 1 -

Источник: https://studfile.net/preview/14517431/

Смотрите также:


ЦЕНОВАЯ ПОЛИТИКА ПРЕДПРИЯТИЯ НА ПРИМЕРЕ ООО «ДНС РИТЕЙЛ»
_archivetempпротивовоспалительные
- Обратный порядок следования фаз 4
- Сопротивление изоляции 25
!_Лабораторные_работы_1_сем_ОУТС
!Контрольная работа (задание)
!Фармакология препаратов для терапии заболеваний дыхательных путей
'Electronics Workbench' – алгоритм инструмента моделирования электронных схем
'Новая экономика': российская специфика