2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Решение в целых числах, НОД
Сообщение16.03.2010, 11:59 
Аватара пользователя
Здравствуйте.

Помогите пожалуйста с направлением решения, идеи.

Пусть даны следующие функции:

y=ax+b и z=cx+d

Вопрос: найти такие значения х, при которых НОД(у,z)<>1, если НОД(а,b)=НОД(c,d)=1

Соответственно даны числа а,b,c,d и требуется все решить в целых числах.

НОД - наибольший общий делитель.

Заранее огромное спасибо.

 
 
 
 Re: Решение в целых числах, НОД
Сообщение16.03.2010, 14:42 
Пишете выражение $D= \gcd (y,z)$, подставляете вместо $y,z$ формулы от $x$ и упрощаете. После упрощения получится выражение вида $D = \gcd (A, nx+m)$, откуда $A|nx+m$ - это можно решить перебором делителей $A$.
Например.

 
 
 
 Re: Решение в целых числах, НОД
Сообщение16.03.2010, 21:59 
Можно попробовать так:умножим 1-е уравнение на c,а 2-е на a,и вычтем.В результате получим $cy-az=cb-ad$.Пусть R=НОД(y,z),тогда $y=Rk_1,z=Rk_2$ и НОД$(k_1,k_2)=1$.Следовательно,$R(ck_1-ak_2)=cb-ad$.Видим,что $R|(cb-ad)$.Ясно,что $R>1$,только если $|cb-ad|>1$.Алекс77,дальше продолжите сами.

 
 
 
 Re: Решение в целых числах, НОД
Сообщение17.03.2010, 12:07 
Аватара пользователя
Огромное спасибо :)
Просветили - в принципе все сводится к перебору всех возможных делителей определенного числа.

Если есть возможность еще что-нибудь придумать полегче, чтобы программа была более простой - буду премного благодарен :)

Еще раз ОГРОМНОЕ спасибо !

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group