Мала теорема Ферма. Теорема Ейлера.

Елементарна теорія чисел

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


Мала теорема Ферма — одне з основних тверджень елементарної теорії чисел. Вперше була сформульована в листі французького математика П'єра де Ферма до свого друга Френікля де Бессі 18 жовтня 1640 року. В листі проте не було наведено доведення. Перше відоме доведення подане Лейбніцом у неопублікованих рукописах.

Мала теорема Ферма допускає кілька еквівалентних формулювань.

Формулювання 1. Нехай p - просте, a - ціле, що не ділиться на p. Тоді:

a ^p-1 º 1 (mod p).

Еквівалентним є наступне твердження:

Формулювання 2. Нехай p - просте, a - довільне ціле число. Тоді:

a ^p - a º 0(mod p).

  

Узагальнення 1. Теорема Ейлера була доведенa, що для довільного a взаємно простого з m>1 виконується наступне:

  a^j(m) º 1(mod m).

dе j(m) - функція Ейлера.

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

Доведення  (комбінаторне)

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

ТЕОРЕМИ  ПРО ОСТАЧІ ПРИ ДІЛЕННІ СТЕПЕНІВ НА НАТУРАЛЬНІ ЧИСЛА.

Варто мати на увазі, що квадрати цілих чисел при діленні на 3 або 4 можуть давати остачі лише 0 та 1, куби при діленні на 9 - лише 0,  1 та 8. (Перевірте це са­мостійно). Подібні факти в поєднанні з вдалим вибором числа, остачі при діленні на яке ми розглядаємо, часто допомагають розв'язуванню. З допомогою такого вдалого вибору можна доводити, що число не є простим, можна розв'язувати рівняння в цілих числах.

Перша теорема Вінницького: Якщо квадрат довільного цілого числа поділити на довільну його цифру, то не можна отримати в остачі: 5; 6; 8.

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

Якщо квадрат довільного натурального числа, тобто,  m² = m∙m, поділити на:

m² :2, то отримаємо  тільки такі остачі 0, 1;

m² :3, то отримаємо тільки такі остачі 0, 1 (не можна отримати остачу 2);

m² :4, то отримаємо тільки такі остачі 0, 1; (не можна отримати остачі 2 і 3);

m² :5, то отримаємо тільки такі остачі 0, 1, 4;(не можна отримати остачі 2 і 3);

m² :6, то отримаємо тільки такі остачі 0, 1, 3, 4; (не можна отримати остачі 2 і 5);

m² :7, то отримаємо тільки такі  остачі  0, 1, 2, 4; (не можна отримати остачі 3; 5; 6);

m² :8, то отримаємо тільки такі остачі  0, 1, 4; (не можна отримати остачі 2; 3; 5; 6;7);

m² :9, то отримаємотільки такі  остачі 0, 1, 4, 7; (не можна отримати остачі 2; 3; 5; 6; 8);

m² :10, то отримаємо тільки такі остачі 0, 1, 4, 5, 6, 9;

m² :11, то отримаємо тільки такі остачі 0, 1, 3, 4, 5, 9;

m² :12, то отримаємо тільки такі остачі 0, 1, 4, 9;

m² :13, то отримаємо тільки такі остачі 0, 1, 3, 4, 9, 10, 12;

m² :14, то отримаємо тільки такі остачі 0, 1, 2, 4, 8, 9;

m² :15, то отримаємо тільки такі остачі 0, 1,4, 6,  9, 10;

m² :16, то отримаємо тільки такі  остачі 0, 1, 4, 9;

m² :17, то отримаємо тільки такі остачі 0, 1, 4, 8, 9,15.

 Таким чином не усі цифри можуть бути лишками при діленні.

Друга теорема Вінницького: Якщо куб довільного цілого числа поділити на довільну його цифру, то можна отримати в остачі будь-яку із цифр, окрім 9.

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

 Якщо куб натурального числа, тобто,  m³ = m∙m∙m, поділити на:

 m³ :2, то отримаємо остачі 0, 1;

m³ :3, то отримаємо остачі 0, 1, 2;

m³ :4, то отримаємо остачі 0, 1, 3;(не можна отримати остачу 2);

m³ :5, то отримаємо остачі 0, 1, 2, 3, 4;

m³ :6, то отримаємо остачі 0, 1, 2, 3, 4, 5;

m³ :7, то отримаємо остачі  0, 1, 6;

m³ :8, то отримаємо остачі  0, 1, 3, 5, 7;

m³ :9, то отримаємо остачі  0, 1, 8;

m³ :10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9

 Таким чином усі цифри можуть бути лишками при діленні.

Третя теорема Вінницького: Якщо біквадрат довільного цілого числа поділити на довільну його цифру, то не можна отримати в остачі: 5; 6; 8. (це твердження є прямим наслідком першої теореми Вінницького).

Доведення.  Знайдемо четвіркові лишки, тобто сстачі при діленні четвертих степенів на натуральні числа.

Якщо четверту степінь натурального числа, тобто,  m⁴ = m∙m∙m∙m, поділити на:

m⁴:2, то отримаємо остачі 0, 1;

m⁴:3, то отримаємо остачі 0, 1

m⁴:4, то отримаємо остачі 0, 1;

m⁴:5, то отримаємо остачі 0, 1;

m⁴:6, то отримаємо остачі 0, 1, 3, 4;

m⁴:7, то отримаємо остачі  0, 1, 2, 4;

m⁴:8, то отримаємо остачі  0, 1;

m⁴:9, то отримаємо остачі 0, 1, 4, 7;

m⁴:10, то отримаємо остачі 0, 1, 5, 6;

 Таким чином не усі цифри можуть бути лишками при діленні.

Четверта теорема Вінницького: Якщо п’яту степінь  довільного цілого числа поділити на довільну його цифру, то  можна отримати в остачі довільну цифру.

Доведення. Знайдемо п’ятіркові лишки, тобто  остачі при діленні п’ятих степенів на натуральні числа.

 Якщо п’яту степінь натурального числа, тобто,  m⁵ = m∙m∙m∙m∙m, поділити на:

m⁵:2, то отримаємо остачі 0, 1;

m⁵:3, то отримаємо остачі 0, 1, 2;

m⁵:4, то отримаємо остачі 0, 1, 3;

m⁵:5, то отримаємо остачі 0, 1, 2, 3, 4;

m⁵:6, то отримаємо остачі 0, 1, 2, 3, 4, 5;

m⁵:7, то отримаємо остачі  0, 1, 2, 3, 4, 5, 6;

m⁵:8, то отримаємо остачі  0, 1, 3, 5, 7;

m⁵:9, то отримаємо остачі  0, 1, 2, 4, 5, 7, 8;

m⁵:10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9. 

Таким чином усі цифри можуть бути лишками при діленні.

Узагальнена теорема Вінницького: Якщо будь-яку натуральну степінь  довільного цілого числа поділити на довільну його цифру, то  можна отримати в остачі довільну цифру.

Доведення.Розглянемо таблицю лишків по модулю 100.   

Таблиця Вінницького довжини двоцифрових періодів степенів цифр.

(Степеневі лишки при діленні на 100)

  mⁿ º ab(mod 100).

Основа	2	3	4	5	6	7	8	9
Довжина  двоцифрового періоду  ….аb	21	20	10	1	6	4	20	10
Довжина  одноцифрового періоду  ….аb	4	4	2	1	1	4	4	2
Критерій парності двох цифр лишку	k & 2n	2k & 2n+1	k & 2n	2k & 2n+1	2k+1&2n	2k & 2n+1	k & 2n	2k & 2n+1
m1	02	03	04	05	06	07	08	09
m2	04	09	16	25	36	49	64	81
m3	08	27	64	25	16	43	12	29
m4	16	81	56	25	96	01	96	61
m5	32	43	24	25	76	07	68	49
m6	64	29	96	25	56	49	44	41
m7	28	87	84	25	36	43	52	69
m8	56	61	36	25	16	01	16	21
m9	12	83	44	25	96	07	28	89
m10	24	49	76	25	76	49	24	01
m11	48	47	04	25	56	43	92	09
m12	96	41	16	25	36	01	36	81
m13	92	23	64	25	16	07	88	29
m14	84	69	56	25	96	49	04	61
m15	68	07	24	25	76	43	32	49
m16	36	21	96	25	56	01	56	41
m17	72	63	84	25	36	07	48	69
m18	44	89	36	25	16	49	84	21
m19	88	67	44	25	96	43	72	89
m20	76	01	76	25	76	01	76	01
m21	52	03	04	25	56	07	08	09

Отже, можливі тільки такі степеневі двоцифрові лишки  для степенів цифр: 00, 01,  02, 03, 04, 05, 06, 07, 08, 09, 12,16, 21,23, 24, 25, 27, 28, 29, 32, 36, 41, 43, 44, 47, 48, 49, 52,56, 61, 63, 64, 67, 68, 69, 72,76, 81,83,  84, 88, 89, 92, 96.

Рівняння  x^m º р (mod 100), де р – одноцифрове або двоцифрове ціле число,  має всього  44 розв’язки, тобто р ={0, 1,  2, 3, 4, 5, 6, 7, 8, 9, 12,16, 21,23, 24, 25, 27, 28, 29, 32, 36, 41, 43, 44, 47, 48, 49, 52,56, 61, 63, 64, 67, 68, 69, 72,76, 81,83,  84, 88, 89, 92, 96}.

Алгебраїчна теорія чисел

Алгебраїчна теорія чисел розширює поняття числа. Алгебраїчне число — це корінь многочлена з раціональними коефіцієнтами. Місце цілих чисел посідають цілі алгебраїчні числа, тобто корені многочленів з цілими коефіцієнтами і старшим коефіцієнтом 1. На відміну від цілих чисел, серед алгебраїчних чисел закон однозначності розкладу на прості множники може і не виконуватись.

Аналітична теорія чисел

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

Геометрична теорія чисел. Пошукайте самостійно інформацію про цей розділ теорії чисел.

Завдання для кмітливих.

Варіант 1.

1.    Чи може середнє арифметичне 35 цілих чисел дорівнювати 6,35?

2.    Фірма купила на розпродажі автомобілів на 35% нижче початкової ціни, а продала на 25%  нижче початкової ціни. Скільки відсотків прибутку вона отримала, тобто, скільки відсотків складає прибуток від затрачених грошей?

3.    Знайти усі чотирицифрові числа, які після відкидання першої цифри зменшуються в 19 разів.

4.    Довести, що число вигляду 2011∙2011∙2011∙…∙2011∙2011 не може містити однакову кількість кожної із цифр 1, 2, 3, 4, 5, 6, 7, 8, 9.

5.    Чи можна записати числа  1, 2, 3, 4, 5, 6, 7, 8, 9 у вигляді таблиці 3х3 так, щоб суми будь-яких двох сусідніх чисел по вертикалі і по горизонталі була простим числом.

варіант 2.

1.    Знайдіть значення дробу В∙А∙Р∙Е∙Н∙Ь∙Е /(К∙А∙Р∙Л∙С∙О∙Н), де різні букви – це різні цифри, а між буквами стоїть знак множення.

2.    У Петі в кишені кілька монет. Якщо Петя навмання витягне з кишені 3 монети, серед них обов’язково знайдеться монета номіналом «1 гривня». Якщо Петя навмання витягне з кишені 4 монети, серед них обов’язково знайдеться монета номіналом «2 гривні». Петя витяг з кишені 5 монет. Назвіть ці монети.

3.    «Йде направо – пісню заводить, наліво – казку говорить». Щоб розповісти  казку вченому Коту потрібно 5 хвилин, а щоб заспівати пісню йому потрібно 4 хвилини. О десятій годині ранку вчений Кіт почав розповідати казку. Куди буде йти кіт опівдні?

4.    На острові живуть лицарі, які завжди говорять правду і брехуни, які завжди брешуть. Мандрівник зустрів трьох мешканців острова і запитав кожного з них «Скільки лицарів серед твоїх супутників?»  Перший відповів: «Жодного». Другий сказав: «Один». Що сказав третій.

варіант 3

1.     Чи існують два послідовних натуральних числа, сума цифр кожного з яких ділиться на 7? Відповідь обґрунтуйте.

2.     На зборах були присутні близько 80 школярів. Третина з них – дівчатка, половина з яких навчається у шостому класі.  Із присутніх хлопчиків 5:7 не навчається у шостому класі. Скільки учнів шостого класу були присутніми на зборах?

3.     Із тверджень «Натуральне число а ділиться на 5»,   «Натуральне число а ділиться на 11»,   «Натуральне число а ділиться на 55»,   «а менше 5»,   два істинні, а два – хибні. Знайдіть а.

4. Дмитрик, Віталій,  та Михайлик збирали гриби. ВІталій зібрав грибів на 20% більше, ніж Дмитрик, але на 20% менше, ніж Михайлик. На скільки відсотків більше, ніж Дмитрик зібрав грибів Михайлик? 

5.    Цифру 9, із якої починається в трицифрове число, перенесли на кінець числа. Нове число на 216 менше, ніж попереднє. Яким було початкове число?