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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
 Заголовок сообщения: Возможно ли решить уравнение в целых числах?
СообщениеДобавлено: 07 мар 2014, 00:52 
Не в сети
Начинающий
Зарегистрирован:
07 мар 2014, 00:47
Сообщений: 4
Cпасибо сказано: 5
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

Интересует, есть ли возможно решить уравнение в целых числа вида:

a*xy+b*x+c*y = d

И сразу пример:

3xy+13x+15y = 1951

Возможно ли решить такое уравнения и получить решение в целых числах?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Возможно ли решить уравнение в целых числах?
СообщениеДобавлено: 07 мар 2014, 01:38 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 13565
Откуда: Москва
Cпасибо сказано: 1292
Спасибо получено:
3625 раз в 3182 сообщениях
Очков репутации: 678

Добавить очки репутацииУменьшить очки репутации
Можно, конечно. Допустим в примере выразим икс:

[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
Изображение

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Avgust "Спасибо" сказали:
Bettykorablik, part13an
 Заголовок сообщения: Re: Возможно ли решить уравнение в целых числах?
СообщениеДобавлено: 07 мар 2014, 08:29 
Не в сети
Последняя инстанция
Аватара пользователя
Зарегистрирован:
29 окт 2010, 11:15
Сообщений: 2790
Откуда: СССР
Cпасибо сказано: 120
Спасибо получено:
857 раз в 688 сообщениях
Очков репутации: 203

Добавить очки репутацииУменьшить очки репутации
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 решений.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю dr Watson "Спасибо" сказали:
mad_math, part13an
 Заголовок сообщения: Re: Возможно ли решить уравнение в целых числах?
СообщениеДобавлено: 07 мар 2014, 08:46 
Не в сети
Последняя инстанция
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1440
Cпасибо сказано: 120
Спасибо получено:
612 раз в 484 сообщениях
Очков репутации: 163

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Shadows "Спасибо" сказали:
mad_math, part13an
 Заголовок сообщения: Re: Возможно ли решить уравнение в целых числах?
СообщениеДобавлено: 07 мар 2014, 10:14 
Не в сети
Начинающий
Зарегистрирован:
07 мар 2014, 00:47
Сообщений: 4
Cпасибо сказано: 5
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

Что-то я совсем забыл многое в математике, хоть и программистом работаю уже больше 7 лет ...

Вот тогда ещё 1 пример, столкнулся на уровне криптографии:

30xy +29x+13y=2771127

Возможно-ли математически (без использования ПК и перебора) найти целые корни тут ?

Буду ну очень благодарен за ответ! П.С. - тут всего одно решение.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Возможно ли решить уравнение в целых числах?
СообщениеДобавлено: 07 мар 2014, 10:36 
Не в сети
Последняя инстанция
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1440
Cпасибо сказано: 120
Спасибо получено:
612 раз в 484 сообщениях
Очков репутации: 163

Добавить очки репутацииУменьшить очки репутации
part13an писал(а):
Возможно-ли математически (без использования ПК и перебора) найти целые корни тут ?
Конечно математически, а как же еще? Перебор конечный - перебор делителей конкретного числа - в случае 83134187. Без компютера можно, но туго.
part13an писал(а):
П.С. - тут всего одно решение.
Тут две решения:
[math](-2771140;-1)[/math] и [math](412,223)[/math]

Shadows писал(а):
Перебор конечный - перебор делителей конкретного числа - в случае 83134187
Ну, а если число огромное, как обычно бывает в криптографии... :D1

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Shadows "Спасибо" сказали:
mad_math, part13an
 Заголовок сообщения: Re: Возможно ли решить уравнение в целых числах?
СообщениеДобавлено: 07 мар 2014, 11:10 
Не в сети
Начинающий
Зарегистрирован:
07 мар 2014, 00:47
Сообщений: 4
Cпасибо сказано: 5
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
А можно по-подробнее? "перебор делителей конкретного числа" - как вы это сделали в предыдущем примере, по какому алгоритму?

И если не сложно после x=[math]\frac{d-c \cdot y}{a \cdot y+b}[/math] чуть распишите свои действия.

Спасибо!!!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Возможно ли решить уравнение в целых числах?
СообщениеДобавлено: 07 мар 2014, 11:43 
Не в сети
Последняя инстанция
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1440
Cпасибо сказано: 120
Спасибо получено:
612 раз в 484 сообщениях
Очков репутации: 163

Добавить очки репутацииУменьшить очки репутации
Решаю уравнение относительно одной из переменных:
[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

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Shadows "Спасибо" сказали:
mad_math, part13an
 Заголовок сообщения: Re: Возможно ли решить уравнение в целых числах?
СообщениеДобавлено: 07 мар 2014, 12:58 
Не в сети
Начинающий
Зарегистрирован:
07 мар 2014, 00:47
Сообщений: 4
Cпасибо сказано: 5
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Shadows писал(а):
Все делители

Как искались эти делители ? перебор ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Возможно ли решить уравнение в целых числах?
СообщениеДобавлено: 07 мар 2014, 13:24 
Не в сети
Последняя инстанция
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1440
Cпасибо сказано: 120
Спасибо получено:
612 раз в 484 сообщениях
Очков репутации: 163

Добавить очки репутацииУменьшить очки репутации
part13an писал(а):
Как искались эти делители ? перебор ?
Я спросил у вольфрама, но иначе да...

О проблеме факторизации

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

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

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

ivanna

14

786

08 фев 2019, 12:16

Решить уравнение в целых числах

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

nikitalyutenko

3

477

04 фев 2018, 21:39

Решить уравнение в целых числах

в форуме Теория чисел

Roseburrow

1

268

01 июл 2021, 20:30

Решить уравнение в целых числах

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

Andy

3

516

07 янв 2019, 12:06

Решить уравнение в целых числах: [n√2]-[m√2]=2m.

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

rechimport

32

885

28 сен 2019, 21:56

Решить уравнение в целых числах

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

HelloKitty

3

357

04 авг 2017, 09:09

ДИОФАНТОВО УРАВНЕНИЕ РЕШИТЬ В ЦЕЛЫХ ЧИСЛАХ

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

Arhimed455

3

390

25 июн 2019, 20:07

Решить уравнение в целых числах методом цепных дробей

в форуме Теория чисел

SHWEEDY

2

309

03 июл 2020, 18:27

Решить уравнение в целых числах методом цепных дробей

в форуме Теория чисел

SHWEEDY

3

521

28 июн 2020, 11:04

Решить в целых числах

в форуме Теория чисел

AlexSam

14

1188

11 май 2015, 21:26


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



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

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


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

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

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

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