Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
 Заголовок сообщения: Решение задачи AB(A+B)=x
СообщениеДобавлено: 03 июл 2017, 15:49 
Не в сети
Одарённый
Зарегистрирован:
20 дек 2016, 11:08
Сообщений: 153
Cпасибо сказано: 2
Спасибо получено:
6 раз в 5 сообщениях
Очков репутации: -3

Добавить очки репутацииУменьшить очки репутации
Приветствую

Встретилась задача:

[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 и т.д. и сужать возможные варианты решения или доказывать, что решений нет, но это большие портянки записей и очень неуниверсальное решение


Можно ли как-то элегантно решить эту задачу?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение задачи AB(A+B)=x
СообщениеДобавлено: 03 июл 2017, 17:03 
Не в сети
Мастер
Аватара пользователя
Зарегистрирован:
31 мар 2017, 00:16
Сообщений: 206
Cпасибо сказано: 11
Спасибо получено:
76 раз в 70 сообщениях
Очков репутации: 17

Добавить очки репутацииУменьшить очки репутации
Элегантного общего решения может и не существовать: по крайней мере, ряд криптографических методов основаны как раз на сложности разложения больших чисел на простые множители (в результате чего для взлома шифра остаётся только перебор вариантов).

В данном случае так или этак придётся иметь дело с разложением числа в правой части.

Примечание к "общему" случаю - допустим, в правой части указано простое число. Задача заведомо не имеет решения, но чтобы это доказать, нужно доказать, что число в правой части - простое. Насколько мне известно, точных методов доказательства простоты (не считая разложения на множители) нет. Для той же криптографии, где перебор слишком накладен, большие простые числа получают отсеиванием по ряду критериев, в результате чего получаются "промышленные простые числа" - это которые скорее всего простые, но без 100-процентной гарантии.

Приходится признать, что в самом общем случае у нас даже нет метода доказать неразрешимость задачи.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение задачи AB(A+B)=x
СообщениеДобавлено: 03 июл 2017, 17:48 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
В данном случае у нас есть подмога в том, что число должно иметь малый простой множитель: [math]\min(A,B) < \sqrt[3] {\frac x2 }[/math]
что позволяет простым перебором решить вплоть до 100-битных чисел.

Без вычислительных мощностей, увы, не обойтись

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение задачи AB(A+B)=x
СообщениеДобавлено: 03 июл 2017, 19:24 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
18 авг 2013, 14:27
Сообщений: 1978
Откуда: Москва
Cпасибо сказано: 384
Спасибо получено:
1069 раз в 855 сообщениях
Очков репутации: 197

Добавить очки репутацииУменьшить очки репутации
Мне кажется, здесь можно использовать признак делимости на 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.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю radix "Спасибо" сказали:
Shadows
 Заголовок сообщения: Re: Решение задачи AB(A+B)=x
СообщениеДобавлено: 04 июл 2017, 10:28 
Не в сети
Одарённый
Зарегистрирован:
20 дек 2016, 11:08
Сообщений: 153
Cпасибо сказано: 2
Спасибо получено:
6 раз в 5 сообщениях
Очков репутации: -3

Добавить очки репутацииУменьшить очки репутации
Кажется удалось решить в общем виде и просто - действительно надо рассмотреть деление по модулю
Будем делить по модулю 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
А это не выполняется ни для одного значения из таблицы, которую привел выше.
Вывод - уравнение не имеет натуральных решений

Или где-то ошибся в рассуждениях?

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 5 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Решение задачи

в форуме Экономика и Финансы

Alya030395

0

767

28 ноя 2015, 21:26

Решение задачи

в форуме Алгебра

AlexandrKapo

9

141

02 ноя 2023, 10:24

Решение задачи

в форуме Алгебра

kirill_medvedev

2

367

14 июн 2018, 16:59

Решение задачи

в форуме Задачи со школьных и студенческих олимпиад

aNASTASYAYA

1

653

18 май 2014, 11:59

Решение задачи

в форуме Теория вероятностей

Sasha234

3

396

14 дек 2020, 18:03

Решение задачи

в форуме Аналитическая геометрия и Векторная алгебра

dimakozlovskii

8

1006

19 фев 2015, 15:03

Решение задачи

в форуме Аналитическая геометрия и Векторная алгебра

vika19

4

416

11 окт 2020, 22:52

Решение задачи

в форуме Пределы числовых последовательностей и функций, Исследования функций

ifaq466

2

385

15 ноя 2014, 23:17

Решение задачи

в форуме Геометрия

Jus23

3

529

20 май 2015, 21:37

Решение задачи

в форуме Математическая статистика и Эконометрика

hh336hh

1

331

14 мар 2015, 14:03


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 42


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved