Олімпіада з теорії чисел 2016

Тематична олімпіада з комбінаторики: умови та розв’язки

Залишити відповідь

Умови та розв’язки

Міська олімпіада з математики м. Вінниці 2016 року

Завдання 3. (8 клас. Міська олімпіада з математики м. Вінниці 2016 року). Числа р, р²+2 – прості. Довести, що р³+2 теж просте.                                

Доведення. Будь-яке просте число, починаючи з 5 можна подати у вигляді 6m-1 або 6m+1. Доведення цього факту вперше запропонував Колмогоров. Усі натуральні числа  він записав у таблиці. 

Z0	Z1	Z2	Z3	Z4	Z5
6n-6	6n-5	6n-4	6n-3	6n-2	6n-1
…	…	…	…	…	…
-12	-11	-10	-9	-8	-7
-6	-5	-4	-3	-2	-1
0	1	2	3	4	5
6	7	8	9	10	11
12	13	14	15	16	17
18	19	20	21	22	23
24	25	26	27	28	29
…	…	…	…	…	…
6n	6n+1	6n+2	6n+3	6n+4	6n+5
Z0	Z1	Z2	Z3	Z4	Z5

Зверніть увагу на те, що в кожному стовпчику  наведеної таблиці знаходяться натуральні числа тільки одного класу лишків за модулем 6.

У двох класах лишків Z₁(сюди входять числа вигляду 6n+1), Z₅(сюди входять числа вигляду 6n-1) за модулем 6  знаходяться прості числа, окрім двох простих чисел 2 та 3. Але в усіх інших класах лишків за модулем 6   можна знайти  складені числа, а саме у першому стовпчику  Z₀ усі числа кратні 6; у третьому  та п’ятому Z₂  та  Z₄ стовпчиках усі числа кратні 2; у четвертому стовпчику Z₃ усі числа кратні 3.

Перевіримо, для яких натуральних чисел виконується умова задачі.

Таким чином, починаємо з першого простого числа, якщо р = 2 – просте число, то р²+2=2²+2=4+2= 6. – не просте. Просте число  2 не задовольняє умову задачі.

Далі, перевіряємо друге просте число, якщо р = 3 – просте число, то р²+2=3²+2=9+2= 11 -просте. Просте число  3 задовольняє умову задачі. І маємо показати,  що р³+2 теж просте, тобто 3³+2=27+2=29 – просте число.

Покажимо, що тепер жодне інше просте число, починаючи з 5, не задовольняє дві умови на одночасної простоти двох  чисел р, р²+2.

Згідно таблиці Колмогорова просте число, починаючи з 5, можна подати у вигляді 6n+1 або 6n-1(натуральне n>0), тому перевіряємо два випадки:

Якщо р = 6n-1 –просте число, то

р²+2 =(6n-1)²+2 = 36n²-12n +1+2= 36n²-12n +3=3(12n²-4n +1) – це складене число для натурального n>0. Умова простоти числа  р²+2 не виконується.

Якщо р = 6n+1 – просте число, то

р²+2 =(6n+1)²+2 = 36n²+12n +1+2= 36n²+12n +3=3(12n²+4n +1) – це складене число натуральне n>0. Умова простоти числа  р²+2 не виконується.

Отже, доведено, що якщо числа р, р²+2 – прості, то р = 3, а тому

р³+2 = 3³+2=27+2=29 –  просте число. Що і треба було довести.

Задача  5. (10 клас. Міська олімпіада з математики м. Вінниці 2016 року). Скільки існує різних пар цілих чисел х та у від 1 до 1000, для яких (х²+у²)/49 є цілим числом( пари (х; у) і (у; х) вважати однаковими)?

Розв’язування. Зазначимо такий факт, який обгрунтовується з властивості квадратів цілих чисел: а²=(-а)²:  якщо цілочисельна пара (х; у) задовольняє умову задачі, тоді цілочисельні пари (-х; -у); (х; -у) теж задовольняють умову задачі.  Розкладемо на прості множники число 49=7*7. Проаналізуємо ділення цілочисельного виразу  х²+у² на 7.

Подамо цілочисельні змінні х та у  у вигляді остач (лишків) при діленні на 7.

{7m-3; 7m-2; 7m-1; 7m;  7m+1; 7m+2; 7m+3 }.

Запишемо повну множину усіх  остач при діленні цілочисельного виразу  х²+у² на 7. Складемо для цього таблицю остач:(тотожні перетворення виразів для отримання лишків виконайте самостійно)

х2+у2	х=7m-3	х=7m-2	х=7m-1	х=7m	х=7m+1	х=7m+2	х=7m+3
у=7k-3	7р+4	7р+6	7р+3	7р+2	7р+3	7р+6	7р+4
у=7k-2	7р+6	7р+1	7р+5	7р+4	7р+5	7р+1	7р+6
у=7k -1	7р+3	7р+5	7р+2	7р+1	7р+2	7р+5	7р+3
у=7k	7р+2	7р+4	7р+1	7р	7р+1	7р+4	7р+2
у=7k +1	7р+3	7р+5	7р+2	7р+1	7р+2	7р+5	7р+3
у=7k +2	7р+6	7р+1	7р+1	7р	7р+1	7р+4	7р+6
у=7k +3	7р+4	7р+6	7р+3	7р+2	7р+3	7р+6	7р+4

Проаналізувавши цю таблицю, маємо тільки один випадок, коли цілочисельний вираз х²+у² ділиться націло на 7, тобто х=7m,  у=7k. Таким чином, цілочисельний вираз х²+у² поділиться на 49 тоді і тільки тоді,  коли х=7m,  у=7k. 

Виконаємо на цю умову обмеження: 1<=7m<=1000, 1<=7k <=1000.  Отже, 1<=m<=142,  1<=k <=142.

Порахуємо кількість пар цілочисельних пар (х; у), враховуючи  (х; у) і (у; х) вважати однаковими: 

(142*7; 142*7), (142*7; 141*7), (142*7; 140*7),    …, (142*7; 1*7),  142 пари

                            (141*7; 141*7), (141*7; 140*7),    …, (141*7; 1*7), 141 пара

                                                        (140*7; 140*7),    …, (140*7; 1*7), 140 пар

                                                                                      ……….

                                                                                               (1*7; 1*7). 
1 пара

142+141+140+…2+1= 142*143/2=10153.

Відповідь: 10153 пар.

Завдання міської олімпіади м. Вінниці 2016 року можна отримати тут:

Завантажити  

Критерії та розв'язки