Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 5 ] |
|
Автор | Сообщение | |
---|---|---|
Fireman |
|
|
Встретилась задача: [math]x \times y \times (x + y) = 2007000002008[/math] x,y - натуральные найти x,y или доказать, что решений нет Решение элементарно, если разложить 2007000002008 на простые множители 2007000002008 [math]2007000002008 = 8 \times 16427 \times 15272113[/math] отсюда вытекает, что целочисленных решений нет Но если усложнить условие - у меня нет вычислительных мощностей или таблиц, чтобы разложить на простые числа, поэтому надо решать каким-то другим способом. Но каким? Есть ли простое и универсальное решение? Например, если x,y - четные, то получаем [math]a = 2 \times x[/math] [math]b = 2 \times y[/math] [math]x \times y \times (x + y) = 2007000002008[/math] [math]a \times b \times (a + b) = 2007000002008 \div 8 = 250875000251[/math] а это невозможно, потому что при любых а,b будет получаться чётное число если а - нечетное, б - четное или а и b - нечетные, то можно попробовать анализировать деление по модулю на 3,9 и т.д. и сужать возможные варианты решения или доказывать, что решений нет, но это большие портянки записей и очень неуниверсальное решение Можно ли как-то элегантно решить эту задачу? |
||
Вернуться к началу | ||
Xmas |
|
|
Элегантного общего решения может и не существовать: по крайней мере, ряд криптографических методов основаны как раз на сложности разложения больших чисел на простые множители (в результате чего для взлома шифра остаётся только перебор вариантов).
В данном случае так или этак придётся иметь дело с разложением числа в правой части. Примечание к "общему" случаю - допустим, в правой части указано простое число. Задача заведомо не имеет решения, но чтобы это доказать, нужно доказать, что число в правой части - простое. Насколько мне известно, точных методов доказательства простоты (не считая разложения на множители) нет. Для той же криптографии, где перебор слишком накладен, большие простые числа получают отсеиванием по ряду критериев, в результате чего получаются "промышленные простые числа" - это которые скорее всего простые, но без 100-процентной гарантии. Приходится признать, что в самом общем случае у нас даже нет метода доказать неразрешимость задачи. |
||
Вернуться к началу | ||
swan |
|
|
В данном случае у нас есть подмога в том, что число должно иметь малый простой множитель: [math]\min(A,B) < \sqrt[3] {\frac x2 }[/math]
что позволяет простым перебором решить вплоть до 100-битных чисел. Без вычислительных мощностей, увы, не обойтись |
||
Вернуться к началу | ||
radix |
|
|
Мне кажется, здесь можно использовать признак делимости на 3.
Число в правой части имеет остаток 1 при делении на 3. Пусть r1 и r2 остатки при делении на 3 чисел х и у. Тогда левая часть сравнима по модулю 3 со следующим выражением: r1 * r2 * ( r1 + r2 ) Перебором возможных значений r1 и r2 убеждаемся, что r1=2 и r2=2. Теперь используем признак делимости на 9. Число в правой части имеет остаток 1 при делении на 9. Используя то, что числа х и у имеют остаток 2 при делении на 3, получаем, что они могут иметь следующие остатки при делении на 9: 2, 5, 8. Снова рассмотрим выражение r1 * r2 * ( r1 + r2 ) Перебором убеждаемся, что невозможно получить остаток 1 при делении на 9. |
||
Вернуться к началу | ||
За это сообщение пользователю radix "Спасибо" сказали: Shadows |
||
Fireman |
|
|
Кажется удалось решить в общем виде и просто - действительно надо рассмотреть деление по модулю
Будем делить по модулю 9 A*B*(A+B) = 2007000002008 ( A*B*(A+B) ) mod 9 = 2007000002008 mod 9 = 1 Это возможно только когда A, B и (A+B) по модулю дают: A B A+B 1 1 1 1 2 5 1 4 7 1 5 2 1 7 4 1 8 8 2 2 7 2 4 8 2 5 1 2 7 2 2 8 4 4 4 4 4 5 5 4 7 1 4 8 2 5 5 4 5 7 8 5 8 7 7 7 7 7 8 5 8 8 1 но при этом (A+B) mod 9 = A mod 9 + B mod 9 А это не выполняется ни для одного значения из таблицы, которую привел выше. Вывод - уравнение не имеет натуральных решений Или где-то ошибся в рассуждениях? |
||
Вернуться к началу | ||
[ Сообщений: 5 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Решение задачи
в форуме Экономика и Финансы |
0 |
767 |
28 ноя 2015, 21:26 |
|
Решение задачи
в форуме Алгебра |
9 |
141 |
02 ноя 2023, 10:24 |
|
Решение задачи
в форуме Алгебра |
2 |
367 |
14 июн 2018, 16:59 |
|
Решение задачи | 1 |
653 |
18 май 2014, 11:59 |
|
Решение задачи
в форуме Теория вероятностей |
3 |
396 |
14 дек 2020, 18:03 |
|
Решение задачи | 8 |
1006 |
19 фев 2015, 15:03 |
|
Решение задачи | 4 |
416 |
11 окт 2020, 22:52 |
|
Решение задачи
в форуме Пределы числовых последовательностей и функций, Исследования функций |
2 |
385 |
15 ноя 2014, 23:17 |
|
Решение задачи
в форуме Геометрия |
3 |
529 |
20 май 2015, 21:37 |
|
Решение задачи | 1 |
331 |
14 мар 2015, 14:03 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 42 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |