середа, 24 червня 2015 р.

Завдання 1 із ТЮМ-2015. Властивості натуральних чисел вигляду а^n -1


http://olga-kozachok.wixsite.com/matemat/blank-15

Властивості  натуральних чисел  вигляду аn -1




Зауваження. Число 241- просте число, тому значення функції Ейлера від цього число - це 240. 
Узагальнення проблеми:
Два прості числа Vp- та Vp+ називатимемо вінницькими близнюками, ящо кожне з них можна відповідно записати:
Vp- = 2р-р  та  Vp+ = 2р+р,
де р – просте число.
Такі числа існують!
 Наприклад:  23-3=5  і  23+3=11, 
при цьому 11-5=2*3. 
Властивості: 1а) Vp+ - Vp- = 2р+р - 2р+р =2р- складене число;
1б) Vp+ +Vp- = 2р+р + 2р-р =2р+1 -складене число;

2) Vp+ * Vp- = (2р+р)(2р-р) =4р-р2 -складене число;
Два прості числа Vp- та Vp+ вигляду називатимемо далекими близнюками, ящо кожне з них можна відповідно записати:
Vp- = 2р-q  та  Vp+ = 2р+q,
де р i q – прості числа.
Властивість: 1а) Vp+ - Vp- = 2р+q - 2р+q =2q- складене число;
1б) Vp+ +Vp- = 2р+р + 2р-р =2р+1 -складене число;
2) Vp+ * Vp- = (2р+q)(2р-q) =4р-q2 -складене число;

Чи існує безліч далеких близнюків?

Чи існує безліч вінницьких близнюків?
Volodymyr Nekrashevych Якщо p непарне, то 2^p=-1 (mod p). Якщо p не ділиться на 3, то або p=1 (mod p), або p=-1 (mod p), отже або 2^p+p, або 2^p-p ділиться на 3. Отже, або p=2, або одне із чисел p, 2^p+p, 2^p-p дорівнює 3. Тому ваш приклад насправді єдиний. Існує тльки одна пара вінницьких близнюків.
Узагальнення проблеми Кармайкла:
Нехай р, q – прості натуральні числа.  Четвірку чисел (р, q, s, t) - називатимемо вичурною квадрою, якщо для неї виконується рівність:  
pqs -1= qt, 
де s, t - деякі натуральні числа.

Така вичурна квадра (41, 3, 2, 2735) існує:  

413*2-1=3*5*547.
Чи скінчена кількість вичурних квадр?




Число Кармайкла
У теорії чисел кармайклове число це додатне складене число n, що задовольняє умову \ b^{n-1} \equiv 1\pmod{n} для всіх цілих b,взаємно простих з n.
Названі в честь американського математика Роберта Кармайкла, що у 1910 році знайшов перше і найменше таке число, 561.

Загальне уявлення

Мала теорема Ферма стверджує, що будь-яке просте число задовольняє вище вказану властивість. У цьому сенсі числа Кармайклаподібні простим. Тому вони називаються псевдопростими числами.
Еквівалентне визначення чисел Кармайкла дає критерій Корсельта.
Теорема (Корсельт, 1899) : Складене число n є числом Кармайкла тоді і тільки тоді, коли n вільне від квадратів і для всіх простихдільників p числа n вірно p − 1 | n − 1 (позначення а | b означає, що а ділить b).
З цієї теореми випливає, що всі числа Кармайкла непарні, оскільки будь-яке парне складене число, вільне від квадратів, має принаймні одного непарного простого дільника, і тому з p − 1 | n − 1 випливає, що парне ділить непарне, що невірно - суперечність.
Такі числа Кармайкла:
1105 = 5 \cdot 13 \cdot 17 \qquad (4 \mid 1104; 12 \mid 1104; 16 \mid 1104)
1729 = 7 \cdot 13 \cdot 19 \qquad (6 \mid 1728; 12 \mid 1728; 18 \mid 1728)
2465 = 5 \cdot 17 \cdot 29 \qquad (4 \mid 2464; 16 \mid 2464; 28 \mid 2464)
2821 = 7 \cdot 13 \cdot 31 \qquad (6 \mid 2820; 12 \mid 2820; 30 \mid 2820)
6601 = 7 \cdot 23 \cdot 41 \qquad (6 \mid 6600; 22 \mid 6600; 40 \mid 6600)
8911 = 7 \cdot 19 \cdot 67 \qquad (6 \mid 8910; 18 \mid 8910; 66 \mid 8910).
У 1994 році Альфорс, Ґренвіл і Померанс довели, що для достатньо великих чисел n кількість чесел Кармайкла, що не перевищують n є не меншою n2 / 7. Звідси зокрема випливає нескінченність множини цих чисел.

Властивості[ред. • ред. код]

Числа Кармайкла мають щонайменше три прості додатні множники. Нижче подані найменші такі числа з k = 3, 4, 5, \ldots простими множниками:
k
3561 = 3 \cdot 11 \cdot 17
441041 = 7 \cdot 11 \cdot 13 \cdot 41
5825265 = 5 \cdot 7 \cdot 17 \cdot 19 \cdot 73
6321197185 = 5 \cdot 19 \cdot 23 \cdot 29 \cdot 37 \cdot 137
75394826801 = 7 \cdot 13 \cdot 17 \cdot 23 \cdot 31 \cdot 67 \cdot 73
8232250619601 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 31 \cdot 37 \cdot 73 \cdot 163
99746347772161 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 31 \cdot 37 \cdot 41 \cdot 641
Перші числа Кармайкла з чотирма простими множниками:
i
141041 = 7 \cdot 11 \cdot 13 \cdot 41
262745 = 3 \cdot 5 \cdot 47 \cdot 89
363973 = 7 \cdot 13 \cdot 19 \cdot 37
475361 = 11 \cdot 13 \cdot 17 \cdot 31
5101101 = 7 \cdot 11 \cdot 13 \cdot 101
6126217 = 7 \cdot 13 \cdot 19 \cdot 73
7172081 = 7 \cdot 13 \cdot 31 \cdot 61
8188461 = 7 \cdot 13 \cdot 19 \cdot 109
9278545 = 5 \cdot 17 \cdot 29 \cdot 113
10340561 = 13 \cdot 17 \cdot 23 \cdot 67

Розподіл[ред. • ред. код]

Нехай C(X) позначає кількість чисел Кармайкла, менших за X. Ердеш довів у 1956 році, що
C(X) < X \exp{\frac{-k \log{X} \log{\log{\log{X}}}}{\log{\log{X}}}}
для деякої константи k;
У наступній таблиці наведені наближені значення цієї константи:
nk
1042.19547
1061.97946
1081.90495
10101.86870
10121.86377
10141.86293
10161.86406
10181.86522
10201.86598

Цікаві факти[ред. • ред. код]

Друге число Кармайкла (1105) може бути подане як сума двох квадратів більшою кількістю способів, ніж будь-яке менше число. Третє число Кармайкла (1729) є числом Рамануджана — Харді (найменше число, що можна записати у вигляді суми двох кубів двома способами).
1729 = 1^3+12^3 = 9^3+10^3

Джерела[ред. • ред. код]

  • Chernick, J. (1935). On Fermat's simple theorem. Bull. Amer. Math. Soc. 45, 269–274.
  • Ribenboim, Paolo (1996). The New Book of Prime Number Records.
  • Löh, Günter and Niebuhr, Wolfgang (1996). A new algorithm for constructing large Carmichael numbers(pdf)
  • Korselt (1899). Problème chinois. L'intermédiaire des mathématiciens, 6, 142–143.
  • Carmichael, R. D. (1912) On composite numbers P which satisfy the Fermat congruence a^{P-1}\equiv 1\bmod P. Am. Math. Month. 19 22–27.
  • Erdős, Paul (1956). On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4, 201 –206.
Відомі факти для подільності  чисел.
Усі натуральні  числа можна записати так:  а)   5k-2,  5k-1, 5k, 5k+1, 5k+2;  б)  6k-3,  6k-2,  6k-1, 6k, 6k+1, 6k+2; 
Простими числами можуть бути числа  6k-1 та 6k+1,  якщо k  – натуральне  число.
аb(а ± b)=2k – це парне число.
аb(а4 –b4)=30k; 
n5 –n =5k; 
n7 –n =7k;   
n2 + m2 + r2+1=8k;
(2k+1)2 –(2n-1)2 =8k;
n(n+1)= 2k, тобто, добуток двох послідовних цілих чисел завжди парне число;
(n+2)(n+1)n = 3k, тобто, добуток трьох послідовних цілих чисел завжди ділиться на 3 націло;
(n-1)n(n+1) = 6k, тобто, добуток трьох послідовних цілих чисел завжди ділиться на 6 націло;
(n-1)n(n+1)(n+2) = 6k тобто, добуток трьох послідовних цілих чисел завжди ділиться на 6 націло;
(n-2)(n-1)n(n+1)(n+2) = 2∙3∙4∙5k=120k, тобто, добуток п’яти послідовних цілих чисел завжди ділиться на 120 націло.
Для всіх простих чисел р> 2000 сума  12000 + 22000+32000 +42000 +…+(р-1)2000

ділиться на просте число р.

СТЕПЕНЕВІ ЛИШКИ. Доведення малої теореми Ферма.

Теорема Ейлера. Якщо  m>1,  НСД(a, m) =1 справедлива конгруенція aj(m) º1(mod m),  де j(m) – функції Ейлера.

Мала теорема Ферма. Якщо  р - просте число,  НСД(a, р) =1 справедлива конгруенція aр-1 º1(mod р),  бо j(р) = р-1– для функції Ейлера.
Мала теорема Ферма — одне з основних тверджень елементарної теорії чисел. Вперше була сформульована в листі французького математика П'єра де Ферма до свого друга Френікля де Бессі 18 жовтня 1640 року. В листі проте не було наведено доведення. Перше відоме доведення подане Лейбніцом у неопублікованих рукописах
Мала теорема Ферма допускає кілька еквівалентних формулювань.

Нехай \ p — просте, \ a — ціле, що не ділиться на \ p. Тоді:
\ a^{p-1} \equiv 1 \pmod{p}.
Еквівалентним є наступне твердження:
Нехай \ p — просте, \ a — довільне ціле число. Тоді:
\ a^p - a \equiv 0 \pmod p.

Узагальнення 1[ред. • ред. код]

Ейлером було доведено, що для довільного \ a взаємно простого з \ m>1 виконується наступне:
a^{\varphi \left ( m \right )} \equiv 1 \pmod{m} \!

Узагальнення 2[ред. • ред. код]

Рівність x^q=x \! справедлива для всіх елементів \ x скінченного поля k_q \!, утвореного \ q елементами.

Доведення[ред. • ред. код]

Доведення 1 (за методом математичної індукції)[ред. • ред. код]

Позначимо, як звично
{p \choose k} = \frac{p(p-1)(p-2)\cdots (p-k+1)}{k!}  — біноміальний коефіцієнт.
Тоді для простого \ p і \ 0<k<p маємо, що {p \choose k} ділиться на \ p . Справді можна записати {p \choose k}= \frac{pm}{k!}\quad\quad,  де \quad\quad m=(p-1)(p-2)\cdots (p-k+1). Оскільки \ p і \ k!  є взаємно-простими, то, очевидно, що \ k! ділить \ m  і, як наслідок {p \choose k}ділиться на \ p . Твердження Малої теореми Ферма доводитимемо методом математичної індукції. Теорема очевидно справедлива для \ a=1 . Припустимо, що вона справджується для певного цілого \ a. Згідно з формулою бінома Ньютона, використовуючи раніше доведене і припущення індукції одержуємо:
(a+1)^p \equiv a^p + a^0 + \sum_{k=1}^{p-1}{p \choose k}a^k \equiv a^p + 1 \equiv a + 1\pmod{p}.
тобто (a+1)^p - (a+1) \equiv 0 \pmod p, що доводить твердження для додатніх цілих. Для від'ємних доведення аналогічне.

Доведення 2 (використовуючи лишки)[ред. • ред. код]

Припустимо, що \ a додатне число, що не ділиться на \ p. Якщо записати
a, 2a, 3a, \ldots, (p-1)a \quad\quad
і обрахувати одержану послідовність за модулем \ p , то ми отримаємо деяку перестановку чисел:
1, 2, 3, \ldots, p-1. \quad\quad\quad .
Справді, жодне з чисел a, 2a, 3a, \ldots, (p-1)a  не ділиться на \ p, оскільки і \ a і будь-яке з чисел 1, 2, 3, \ldots, p-1. є взаємно прості з \ p . Далі всі числа  a, 2a, \ldots,(p-1)a  мають бути відмінними одне від одного за модулем \ p. Справді, якщо
ka \equiv ma \pmod p, \,\!
де \ k  і \ m  належать множині чисел  1, 2,\ldots, (p-1)  то, зважаючи на взаємну простоту \ a і \ p отримуємо:
k \equiv m \pmod p. \,\!, що неможливо.
Відповідно, якщо ми перемножимо обидві послідовності, то результати повинні бути еквівалентні за модулем \ p:
a \times 2a \times 3a \times \cdots \times (p-1)a \equiv 1 \times 2 \times 3 \times \cdots (p-1) \pmod p.
Після перестановки множників і перепозначення отримуємо:
\ a^{p-1} (p-1)! \equiv (p-1)! \pmod p.
Остаточно, зважаючи, що \ p і \ (p-1)! взаємно-прості одержуємо твердження теореми:
a^{p-1} \equiv 1 \pmod p.\,\!

Доведення 3 (комбінаторне)[ред. • ред. код]

Припустимо, що ми маємо бусинки \ a  різних кольорів і нам потрібно зробити з них намисто довжиною \ p  бусинок. Для початку зробимо стрічку з \ p  бусинок. Існує \ a^p  різних стрічок. Відкинемо всі однотонні стрічки їх всього \ a . Залишеться \ a^p-a  різних стрічок. З'єднаємо початок кожної стрічки з її кінцем. Тепер деякі намиста стали однаковими, якщо їх повернути. Оскільки існує \ p  різних циклічних перестановок то існує \ \frac{a^p-a}{p}  різних намист. Виходячи з інтерпретації числа \ \frac{a^p-a}{p}  воно ціле.



Найменше натуральне число  k називають показником, до якого належить число а за модулем m  тоді , коли має місце конгруенція 
akº1(mod m),
при цьому k<=j(m) – функції Ейлера і НСД(а; m)=1.
Властивості показників:
1.Якщо числа конгруентні за модулем m, то вони належать до одного і того самого показника.
Якщо  a=b(mod m),    і    ak=1(mod m), то  bk=1(mod m),
2.Якщо а належить до показника  k за модулем m, то у ряді степенів  a0 , a1 , a2 , a3 , …., ak-1 всі числа не конгруентні одне з одним за модулем m.
3.Якщо а належить до показника  k за модулем m, то коенгруенція  ak1= аk2 (mod m) має місце тільки тоді, коли k1=k2(mod k).
4.Якщо а належить до показника  k за модулем m, то k – буде дільником j(m) функції Ейлера.
4.Якщо а належить до показника  k = j(m) за модулем m, то а називають первісним коренем.  Числа a0 , a1 , a2 , a3 , …., ak-1 є розв′язками конгруенції  хk=1(mod p),  тобто k = j(р)=р-1. Отже,  первісних коренів шукаємо серед розв′язків конгруенції
хр-1=1(mod p),  де р – просте число. Число первісних коренів згідно з теоремою Гауса буде  j(р-1).

Опубліковано о

Немає коментарів:

Дописати коментар

Підписатися на: Дописати коментарі (Atom)