Question

Найдите наибольшее натуральное n при котором число 2010!=1*2*3.....2009*2010 делится на n^4

Answer 1

Будем искать наименьшее неподходящее. Понятно, что это число имеет вид p^k, где p - простое (иначе оно бы разбивалось на произведение двух взаимно простых множителей, больших единицы, являющихся, по предположению, делителем 2010!)

Простое число p входит в разложение числа 2010! на простые множители в степени [2010/p] + [2010/p^2] + [2010/p^3] + ... ([x] - целая часть x)

Посмотрим, какие степени выходят для маленьких простых чисел p.

В наибольшей степени в произведение входит двойка, её степень равна
[2010/2] + [2010/4] + [2010/8] + ... + [2010/1024] = 2002
Для p = 2 максимальное возможное k есть [2002/4] = 500.

Дальше тройка:
[2010/3] + [2010/9] + [2010/81] + ... + [2010/729] = 1001
Для p = 3 максимальное возможное k есть [1001/4] = 250

Пятерка:
[2010/5] + [2010/25] + [2010/125] + [2010/625] = 501
Для p = 5 максимальное возможное k есть [501/4] = 125

Семерка:
[2010/7] + [2010/49] + [2010/343] = 333
Для p = 7 максимальное возможное k есть [333/4] = 83

Сравним числа 2^501 > 3^251 > 5^126 > 7^84.
(Их десятичные логарифмы: 346.5 > 274.7 > 201.2 > 161.5)

Возникает гипотеза: для нашего случая k = 1. Найдем подходящее число p.
Итак, надо найти такое простое p, что предыдущее простое входит в степени, не меньшей четырех, а p - в степени не большей трех. Заметим, что p^2 < 2010 - иначе число p входит в разложение в степени, не меньшей, чем (p - 1), что куда больше четырех при больших p.
[2010/p] + [2010/p^2] + ... = [2010/p] < 4
p > 2010/4
Минимальное простое p, удовлетворяющее неравенствам, равно 503.

На этом мотивировочная часть решения закончилась и начинается решение.

РЕШЕНИЕ. 
Утверждаем, что это число равно 503.
Заметим, что для всех n < 503 числа n, 2n, 3n, 4n < 2010 и поэтому 2010! делится на 24n^4 и, в частности, на n^4. Но 2010! делится на 503^3 и не делится на 503^4.

Answer 2

Для найменшого n, що є натуральним числом, при якому 2010! ділиться на n^4, потрібно враховувати, які прості числа містяться в розкладі 2010!. Це можна зробити за допомогою теореми Лежандра:

Теорема Лежандра: Кількість простих чисел p, які ділять n! (n-факторіала), дорівнює сумі часток цілих чисел n/p, n/p^2, n/p^3, ... до тих пір, поки n/p^k не стане меншим або рівним 1.

Тепер ми можемо знайти розклад 2010! на прості множники та їх кількість для кожного простого числа p:

1. Розклад на прості множники 2010!:

2010! = 2^m * 3^n * 5^p * ...

2. Знайдемо кількість простих множників для кожного простого числа:

Для числа 2: m = [2010/2] + [2010/4] + [2010/8] + ... = 1005 + 502 + 251 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 2002.

Для числа 3: n = [2010/3] + [2010/9] + [2010/27] + ... = 670 + 74 + 8 + 0 = 752.

Для числа 5: p = [2010/5] + [2010/25] + ... = 402 + 80 + 16 + 3 + 0 = 501.

3. Тепер знайдемо найбільше n таке, що 2010! ділиться на n^4:

n^4 = 2^(4m) * 3^(4n) * 5^(4p).

Максимальний n буде дорівнювати найменшому експоненті у цьому розкладі:

n = min(4m, 4n, 4p) = min(42002, 4752, 4*501) = min(8008, 3008, 2004) = 2004.

Таким чином, найбільше натуральне n, при якому 2010! ділиться на n^4, дорівнює 2004.