Математический форум 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
a=3
b=13
c=15
d=1951
for y=-n to n
x=(d-c*y)/(a*y+b)
if x=int(x) then
print x,y
fi
next y


Получим сколько угодно пар целых чисел в зависимости от размаха циклов 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
Ну, а если число огромное, как обычно бывает в криптографии... :D1

Автор:  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/