| Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
| Возможно ли решить уравнение в целых числах? http://mathhelpplanet.com/viewtopic.php?f=10&t=31446 |
Страница 1 из 1 |
| Автор: | part13an [ 07 мар 2014, 00:52 ] |
| Заголовок сообщения: | Возможно ли решить уравнение в целых числах? |
Доброго времени суток! Интересует, есть ли возможно решить уравнение в целых числа вида: a*xy+b*x+c*y = d И сразу пример: 3xy+13x+15y = 1951 Возможно ли решить такое уравнения и получить решение в целых числах? |
|
| Автор: | Avgust [ 07 мар 2014, 01:38 ] |
| Заголовок сообщения: | Re: Возможно ли решить уравнение в целых числах? |
Можно, конечно. Допустим в примере выразим икс: [math]x=\frac{1951-15y}{3y+13}[/math] Теперь просто подставляем произвольное y и смотрим, будет ли икс целым. Например, уже при [math]y=1\, ; \, x=121[/math] Решения будут при y= 5, 33, -79, -23, -15, -9 ... Бесконечно много решений. Общая формула [math]x=\frac{d-c \cdot y}{a \cdot y+b}[/math] Нашу задачу легко запрограммировать: n=200 Получим сколько угодно пар целых чисел в зависимости от размаха циклов n В данном случае будем иметь такие пары x и y
|
|
| Автор: | dr Watson [ 07 мар 2014, 08:29 ] |
| Заголовок сообщения: | Re: Возможно ли решить уравнение в целых числах? |
Avgust писал(а): Бесконечно много решений. Отнюдь. Уравнение представимо в виде [math](x+5)(3y+13)=2^5\cdot 3^2\cdot 7[/math] Отсюда следует разложить [math]2^5\cdot 3^2\cdot 7[/math] на множители [math]a[/math] и [math]b[/math], причем [math]b\equiv 1\pmod 3[/math], и из равенств [math]x+5=a, \ 3x+13=b[/math] найти все решения. Вот все допустимые делители [math]b[/math]: [math]b=1, 4. 16, 7, 7\cdot 4, 7\cdot 16, -2, -8, -32, -7\cdot 2, -7\cdot 8, -7\cdot 2[/math] Итого - 12 решений. |
|
| Автор: | Shadows [ 07 мар 2014, 08:46 ] |
| Заголовок сообщения: | Re: Возможно ли решить уравнение в целых числах? |
Ничего не надо запрограмировать. [math]x=\frac{-15y+1951}{3y+13}=-5+\frac{2016}{3y+13}[/math] Все делители 2016 вида [math]3k+1[/math] дают решение [math]2016=2^5\cdot 3^2\cdot 7[/math], а следователно решения будут при [math]3y+13=1,-2,4,-8,16,-32,7,-14,28,-56,112,-224[/math] Я практически дублировал сообщение dr Watson. Разложить на множители или "делить уголком" - дело вкуса, на практике одно и тоже. |
|
| Автор: | part13an [ 07 мар 2014, 10:14 ] |
| Заголовок сообщения: | Re: Возможно ли решить уравнение в целых числах? |
Спасибо всем за участи Что-то я совсем забыл многое в математике, хоть и программистом работаю уже больше 7 лет ... Вот тогда ещё 1 пример, столкнулся на уровне криптографии: 30xy +29x+13y=2771127 Возможно-ли математически (без использования ПК и перебора) найти целые корни тут ? Буду ну очень благодарен за ответ! П.С. - тут всего одно решение. |
|
| Автор: | Shadows [ 07 мар 2014, 10:36 ] |
| Заголовок сообщения: | Re: Возможно ли решить уравнение в целых числах? |
part13an писал(а): Возможно-ли математически (без использования ПК и перебора) найти целые корни тут ? Конечно математически, а как же еще? Перебор конечный - перебор делителей конкретного числа - в случае 83134187. Без компютера можно, но туго.part13an писал(а): П.С. - тут всего одно решение. Тут две решения:[math](-2771140;-1)[/math] и [math](412,223)[/math] Shadows писал(а): Перебор конечный - перебор делителей конкретного числа - в случае 83134187 Ну, а если число огромное, как обычно бывает в криптографии...
|
|
| Автор: | part13an [ 07 мар 2014, 11:10 ] |
| Заголовок сообщения: | Re: Возможно ли решить уравнение в целых числах? |
А можно по-подробнее? "перебор делителей конкретного числа" - как вы это сделали в предыдущем примере, по какому алгоритму? И если не сложно после x=[math]\frac{d-c \cdot y}{a \cdot y+b}[/math] чуть распишите свои действия. Спасибо!!! |
|
| Автор: | Shadows [ 07 мар 2014, 11:43 ] |
| Заголовок сообщения: | Re: Возможно ли решить уравнение в целых числах? |
Решаю уравнение относительно одной из переменных: [math]x=\frac{-cy+d}{ay+b}[/math] Сейчас нужно освободиться от y в числителе. Если (a,c) взаимнопростые и (a,b) тоже, домножаю числитель на а (потом результат придется конечно поделить на "а") [math]-acy+d \div ay+b=-c+\frac{ad+cb}{ay+b}[/math] Или [math]x=\frac 1 a\left(-c+\frac{ad+cb}{ay+b}\right)[/math] И рассматриваем делители числа [math]ad+cb[/math], будут ли среди них такие [math]d \equiv b \pmod a[/math] В конкретном случае [math]ad+cb=83134187=6719\times 12373[/math] Все делители:[math]\pm 1,\pm 6719,\pm 12373,\pm 83134187[/math] Среди них ищем [math]-1 \pmod{30}[/math] Такими являются -1, 6719 [math]30y+29=-1[/math] [math]30y+29=6719[/math] Находим y, ну и потом x |
|
| Автор: | part13an [ 07 мар 2014, 12:58 ] |
| Заголовок сообщения: | Re: Возможно ли решить уравнение в целых числах? |
Shadows писал(а): Все делители Как искались эти делители ? перебор ? |
|
| Автор: | Shadows [ 07 мар 2014, 13:24 ] |
| Заголовок сообщения: | Re: Возможно ли решить уравнение в целых числах? |
part13an писал(а): Как искались эти делители ? перебор ? Я спросил у вольфрама, но иначе да...О проблеме факторизации |
|
| Страница 1 из 1 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|