Докажите что число 5 2016 28 составное

Докажите, что
а) 2 41 + 1 делится на 83;
б) 2 70 + 3 70 делится на 13;
в) 2 60 – 1 делится на 20801.

Решение

а) 2 9 = 512 ≡ 14 (mod 83), 2 18 ≡ 196 ≡ 30, 2 36 ≡ 900 ≡ 70 ≡ –13, 2 41 ≡ –13·32 ≡ –416 ≡ –1.

б) 2 70 + 3 70 = 4 35 + 9 35 делится на 4 + 9 = 13.

в) 20801 = 11·31·61.
Первый способ. 2 60 – 1 делится на 2 10 – 1 = (2 5 – 1)(2 5 + 1) = 31·33. Это число делится на 31 и на 11. Кроме того, 2 6 ≡ 3 (mod 61), 2 30 ≡ 243 ≡ –1,
2 60 ≡ 1.
Второй способ. Согласно малой теореме Ферма (см. задачу 60736) 2 60 – 1 делится на 61, 2 30 – 1 делится на 31, 2 10 – 1 делится на 11. Поэтому
2 60 – 1 делится на все эти числа.

Замечания

В п. а) школьники, знакомые с квадратичными вычетами могут рассуждать так: (2 41 – 1)(2 41 + 1) = 2 82 – 1 делится на 83 по малой теореме Ферма. Двойка не является квадратичным вычетом по модулю 83, поэтому 2 41 – 1 на 83 не делится. Значит, на 83 делится 2 41 + 1.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	2
Название	Делимость
Тема	Теория чисел. Делимость (прочее)
задача
Номер	04.027

Докажите что число 5 2016 28 составное

Полезно запомнить следующее правило: последняя цифра произведения двух чисел равна последней цифре произведения последних цифр сомножителей. В частности, последняя цифра произведения зависит только от последних цифр сомножителей.

а) Начнём выписывать последние цифры степеней двойки. На каждом шаге будем умножать результат предыдущего шага на 2 и, если получается двузначное число, брать его последнюю цифру. Получим: 2 1 = 2, 2 4 =4, 2 3 =8, 2 4 = 16 → 6, 2 5 → 6·2 = 12 → 2, 2 6 → 2· 2 = 4, 2 7 → 4· 2 = 8, 2 8 → 8· 2 = 16 → 6, и т. д. Заметим, что последние цифры чередуются в такой последовательности: 2, 4, 8, 6, 2, 4, 8, 6. При этом последняя цифра степени зависит от того, с каким остатком показатель степени делится на 4. В частности, всегда, когда показатель степени делится на 4 без остатка (как 4, 8, 100), последняя цифра степени равна 6.

б) Последняя цифра числа 549 49 совпадает с последней цифрой числа 9 49 . Последние цифры степеней девятки чередуются так: 9, 1, 9, 1, 9, 1. То есть если показатель степени нечётный, степень оканчивается на 9. Значит, и число 9 49 , и исходное число 549 49 оканчиваются на 9.

в) Последняя цифра числа 2013 2013 совпадает с последней цифрой числа 3 2013 . Последние цифры степеней тройки чередуются так: 3, 9, 7, 1, 3, 9, 7, 1. То есть последняя цифра степени зависит от того, с каким остатком показатель степени делится на 4. В частности, всегда, когда показатель степени делится на 4 с остатком 1 (как 1, 5, 2013), последняя цифра степени равна 3. А значит, и последняя цифра числа 2013 2013 равна 3.

2. В книге рекордов Гиннеса написано, что наибольшее известное простое число равно (23021 337 − 1). Не опечатка ли это?

Решение. Число 23021 337 оканчивается единицей (это проверяется аналогично решению задачи 1). Поэтому последняя цифра числа (23021 337 − 1) равна 0, а значит, это число делится на 10 и потому составное.

3. В магазин привезли 206 литров молока в бидонах по 10 и 17 литров. Сколько было бидонов каждого вида?

Ответ. Семь десятилитровых и восемь семнадцатилитровых.

Решение. Нужно взять несколько слагаемых по 10 л и несколько слагаемых по 17 л так, чтобы сумма была равна 206 л (в частности, чтобы последняя цифра суммы равнялась 6). Количество десятилитровых бидонов не влияет на последнюю цифру суммы. Значит, надо только выяснить, сколько должно быть 17-литровых бидонов, чтобы их суммарный объём оканчивался цифрой 6. Для этого количество 17-литровых бидонов должно оканчиваться на 8 (проверьте, что это правда и что другие варианты не подходят). То есть 17-литровых бидонов может быть 8, 18, 28, и т.д. Но если их хотя бы 18, то их общий объём составляет по крайней мере 18·17 = 306 л, что больше, чем 206 л. Значит, 17-литровых бидонов будет 8, и их общий объём будет равен 136 л. Тогда десятилитровые бидоны должны иметь общий объем 70 л, а для этого их должно быть 7.

4. Делится ли число 47 30 +39 50 на 10?

Решение. Число 47 30 оканчивается цифрой 9, а число 39 50 — цифрой 1 (это проверяется аналогично решению задачи 1). Значит, их сумма оканчивается на 0 и потому делится на 10.

5. Найдите последнюю цифру в произведении всех нечётных чисел от 1 до 2013.

Решение. Это произведение делится на 5, но не делится на 2. Поэтому в силу признаков делимости на 2 и 5 оно может оканчиваться только цифрой 5.

6. Сколькими нулями оканчивается число 2013! = 1·2·3·. ·2011·2012·2013 ?

Если мы разложим число 2013! на простые множители, то количество нулей на конце этого числа будет равно степени, в которой в это разложение входит пятёрка. (В самом деле, 10 = 2·5, а двойка заведомо войдёт в разложение в большей степени, чем пятёрка.)

2013 = 5·402 + 3. Поэтому среди чисел от 1 до 2013 ровно 402 числа делятся на 5. Аналогичным образом выясним, что из этих чисел ещё 80 делятся на 25, то есть на 5 2 , ещё 16 делятся на 125, то есть на 5 3 , и ещё 3 числа делятся на 625, то есть на 5 4 . Итого 402+80+16+3 = 501, то есть в разложение числа 2013! пятёрка входит в степени 501. Поэтому 2013! оканчивается 501 нулём.

7. Докажите, что среди квадратов любых пяти натуральных чисел всегда можно выбрать два, сумма или разность которых делится на 10.

Решение. Квадрат любого натурального числа оканчивается на 0, 1, 4, 5, 6 или 9 (проверяем для чисел от 1 до 10, дальше последние цифры повторяются в той же последовательности). Если в наборе есть два квадрата, оканчивающиеся на две одинаковые цифры, при их вычитании получится число с нулём на конце, а значит, делящееся на 10. Если же все пять последних цифр квадратов в наборе различны, то среди них обязательно будет либо пара (4, 6), либо пара (1, 9). Тогда сложим эти квадраты и тоже получим число с нулём на конце, а значит, делящееся на 10.

8. Найдите последнюю цифру числа 7 7 7 . Степени считаются сверху вниз: 7 7 7 =7 (7 7 ) .

Решение. Последние две цифры числа 7 7 образуют число 43 (это можно вычислить непосредственно, отбрасывая при каждом умножении все цифры результата, кроме последних двух). Значит, число 7 7 делится на 4 с остатком 3. Степени семёрки могут оканчиваться на 7, 9, 3 или 1 (в зависимости от того, с каким остатком делится на 4 показатель степени). В нашем случае 43 делится на 4 с остатком 3, значит, и 7 7 делится на 4 с остатком 3 (согласно признаку делимости на 4). А у всех степеней семёрки, показатели которых делятся на 4 с остатком 3, последняя цифра равна 3.

9. На доске было написано число из нескольких семёрок: 777. 77. Влад стёр у этого числа последнюю цифру, полученное число умножил на 3 и к произведению прибавил стёртую цифру. С полученным числом он проделал ту же операцию, и так далее. Докажите, что через некоторое время у него получится число 7.

Решение. При каждой операции из числа 10 х + у получается число 3 х + у (здесь y — последняя цифра исходного числа). Разность этих чисел равна 10 x + y − (3 x + y ) = 7 х и значит, делится на 7. Значит, при каждом шаге делимость числа на 7 сохраняется (исходное число, очевидно, делилось на 7), а само число уменьшается. Поскольку операцию можно проделывать с любым натуральным числом, в котором больше одной цифры, мы рано или поздно получим однозначное число, кратное 7.

ЗАДАЧИ
6 класс
Письменная работа
Задачи для знакомства
Ацнок с зиланА
Чётность
Делимость
В триодиннадцатом королевстве
Алгоритмы
Математические игры
Движение и работа
Геометрия
Комбинаторика
Комбинаторика — 2
Задачи на повторение
Математическая абака
География и путешествия
Признаки делимости
Последовательности
От противного
Графы
Шахматы
Раскраски
Последняя цифра
Оценка плюс пример
Лингвистика
История математики
ЗАДАЧИ ДОП. НАБОРОВ
Доп. набор 1
Доп. набор 2

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!

Составное число

Два в любой нечётной степени даёт остаток 2 при делении на 3, поэтому число делится на 3.

Докажите что число 5 2016 28 составное

Сообщение LNV » Вс, 05 июн 2016, 21:00

Это форум назван в честь фильма «Математик и чёрт». https://www.youtube.com/watch?v=52yhBkkulXw

Его создали два ученика Сиверской гимназии для решения олимпиадных задач по математике и не только.
______________________________________________________________________________________________________________________________
Также, на этом форуме не возбраняется что-то писать другим людям, увлекающимся математикой.
Мы всегда будем рады вашей помощи .

Последний раз редактировалось LNV Вс, 05 июн 2016, 22:30, всего редактировалось 1 раз.
LNV Сообщения: 45 Зарегистрирован: Вт, 17 ноя 2015, 20:45

Re: Математик и чёрт

Сообщение LNV » Вс, 05 июн 2016, 22:22

Задачи из книги «Целые числа» (Санкт-Петербург, 2009 год).

Тема: Определение и простейшие свойства делимости.
1. Докажите, что число натуральных делителей числа n не превосходит 2 sqrt(n). (sqrt — квадратный корень, программисты поймут )

Тема: Признаки делимости.
1. В записи каждого из чисел a, b (a не равно b) используются все цифры 1,2,3,4,5,6,7, при чём каждая по одному разу. Докажите, что а не делится на b.

Тема: Наибольший общий делитель.
1. Натуральные числа a,b,x и y таковы, что ax+by делится на a 2 +b 2 . Докажите, что числа x 2 +y 2 и a 2 +b 2 имеют общий делитель, больший 1.

Тема: Взаимно простые числа.
1. Найдите НОД(2 n -1, 2 m -1).
2. Пусть m и n — взаимно простые числа. Какие значения может принимать: а) НОД(5m+n, 7m+3n); б) НОД(m+n, m 2 +n 2 )?

Тема: Линейные уравнения с двумя переменными.
1. Решите уравнения в целых числах:
а) 6x 2 -xy-2y 2 =5
б) (x 2 -2)(3x+y)=5x-2y.

Тема: Простые числа.
1. Докажите, что если p — простое число, то остаток от деления p на 30 есть либо 1, либо простое число.
2. Докажите, что всякое простое число, больше 3, имеет либо вид 6n+1, либо вид 6n-1.
3. Найдите все такие простые числа p, что числа p+2, p+4 также являются простыми.
4. Докажите, что если числа p, 2p+1 простые и p>3, то число 4p+1 составное.
5. Докажите, что если числа p, 8p+1 простые, то и число 8p 2 +2p+1 простое.
6. Натуральные числа х и y, большие 1, таковы, что x2+y2-1 делится на x+y-1. Докажите, что x+y-1 — составное число.
7. Натуральные числа a, b и n>1 таковы, что (a+b) n делится на ab. Докажите, что a n-1 делится на b.

Если вы хотите что-то написать по предложенным задачам (например, решение одной из них), то, пожалуйста, укажите тему и номер задачи.

LNV Сообщения: 45 Зарегистрирован: Вт, 17 ноя 2015, 20:45

Re: Математик и чёрт

Сообщение LNV » Пн, 06 июн 2016, 13:07

Задачи из книги «Целые числа» (Санкт-Петербург, 2009 год).

Тема: Линейные уравнения с двумя переменными.
1. Решите уравнения в целых числах:
а) 6x 2 -xy-2y 2 =5
б) (x 2 -2)(3x+y)=5x-2y.

Тема: Простые числа.
1. Докажите, что если p — простое число, то остаток от деления p на 30 есть либо 1, либо простое число.
2. Докажите, что всякое простое число, больше 3, имеет либо вид 6n+1, либо вид 6n-1.
3. Найдите все такие простые числа p, что числа p+2, p+4 также являются простыми.
4. Докажите, что если числа p, 2p+1 простые и p>3, то число 4p+1 составное.
5. Докажите, что если числа p, 8p+1 простые, то и число 8p 2 +2p+1 простое.
6. Натуральные числа х и y, большие 1, таковы, что x 2 +y 2 -1 делится на x+y-1. Докажите, что x+y-1 — составное число.

Тема: Сравнения.
1. Пусть р — простое число. Докажите, что если а р -b р делится на р , то и (а р -b р )/(а-b) делится на р (в книге говорится, что то же верно без предположения простоты, но доказать труднее).
2. Докажите, что если a+b+c делится на 30, то a 5 +b 5 +c 5 делится на 30.
3. Пусть m — простое число, а — целое число, причём а не делится на m . Докажите, что существует такое целое b что ab = 1(mod m ). Обобщите это утверждение на случай составного m .
4. Пусть р — простое число. Докажите, что ( р -1)! = -1(mod p ). (В книге даётся указание: для каждого целого а, 2 < a < p -2, найдите такое целое b, 2 < b < p -2, что a не равно b, ab = 1(mod p ).)
5. Пусть a, m₁,m₂. m_k — целые числа, причём m₁,m₂. m_k попрано взаимно просты. Докажите, что существует такое целое число х , что х = а (mod m₁ ), x = 0(mod m₂ ). x = 0(mod m_k ).
6. Пусть a₁,а₂. а_k, m₁,m₂. m_k — целые числа, причём m₁,m₂. m_k попрано взаимно просты. Докажите, что существует такое целое число x , что х = а₁ (mod m₁ ), x = а ₂ (mod m₂ ). x = a_k (mod m_k ). (В книге даётся указание: воспользуйтесь результатом задачи 10.)
Примечание. Утверждение задачи 6 — это так называемая «Китайская теорема об остатках».

LNV Сообщения: 45 Зарегистрирован: Вт, 17 ноя 2015, 20:45

Re: Математик и чёрт

Сообщение LNV » Вт, 07 июн 2016, 22:19

Задачи из книги «Целые числа» (Санкт-Петербург, 2009 год).

Тема: Линейные уравнения с двумя переменными.
1. Решите уравнения в целых числах:
а) 6x 2 -xy-2y 2 =5
б) (x 2 -2)(3x+y)=5x-2y.

Тема: Простые числа.
1. Докажите, что если p — простое число, то остаток от деления p на 30 есть либо 1, либо простое число.
2. Докажите, что всякое простое число, больше 3, имеет либо вид 6n+1, либо вид 6n-1.
3. Найдите все такие простые числа p, что числа p+2, p+4 также являются простыми.
4. Докажите, что если числа p, 2p+1 простые и p>3, то число 4p+1 составное.
5. Докажите, что если числа p, 8p+1 простые, то и число 8p 2 +2p+1 простое.
6. Натуральные числа х и y, большие 1, таковы, что x 2 +y 2 -1 делится на x+y-1. Докажите, что x+y-1 — составное число.
7. Докажите, что любое целое чётное a > 2 можно представить в виде суммы двух простых чисел.

Докажите что число 5 2016 28 составное

Докажите что число 5 2016 28 составное

Решение

Замечания

Источники и прецеденты использования

Докажите что число 5 2016 28 составное

Составное число

Комментарии

Докажите что число 5 2016 28 составное

Re: Математик и чёрт

Re: Математик и чёрт

Re: Математик и чёрт

Добавить комментарий Отменить ответ