Решение в целых числах, НОД

[Алекс77]

Здравствуйте.

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

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

y=ax+b и z=cx+d

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

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

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

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

[Sonic86]

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

[mihiv]

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

[Алекс77]

Огромное спасибо
Просветили - в принципе все сводится к перебору всех возможных делителей определенного числа.

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

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