Liczba dajaca dana reszte z dzielenia przez cos

[KaMyLuS]

Mamy wyrazenie \(\displaystyle{ \frac{A-x*(N+K)}{K-N}}\), gdzie A, N, K sa podanymi liczbami calkowitymi. Czy jest mozliwosc szybkiego sprawdzenia (tzn bo chce napisac program na to) CZY ISTNIEJE taka liczba x, ze podane wyrazenie da wynik całkowity (lub inaczej -> ze mianownik dzieli licznik bez reszty)? Sprawdzanie wszystkich liczb z zakresu odpada bo jest on, mowiac delikatnie, szeroki.

[BettyBoo]

Jest taka możliwość. Twoje pytanie to pytanie o to, czy równanie diofantyczne \(\displaystyle{ x(N+K)+y(K-N)=A}\) ma rozwiązanie. Rozwiązanie istnieje wtedy i tylko wtedy gdy NWD współczynników dzieli prawą stronę, tzn NWD(N+K, K-N)|A - i to jest jedyny warunek, który trzeba sprawdzić.

Pozdrawiam.

[KaMyLuS]

Jednak jak sie przyjrzałem to troche za gleboko ze swoimi wnioskami poszedlem, ktore doprowadzily mnie do podanego wyzej rownania. A wyszło ono z takiego układu:
\(\displaystyle{ K(a+b) + N(c+d)=X}\)
\(\displaystyle{ K(c-d) + N(a-b)=Y}\)
K,N,X,Y sa podane. I czy w tym przypadku tez sie da stwierdzic czy istnieja calkowite a,b,c,d dla ktorych powyzszy uklad jest spelniony?

[BettyBoo]

Jeśli K,N,X,Y są całkowite to też się da stwierdzić. Każde z równań jest równaniem diofantycznym o 4 niewiadomych i warunek rozwiązalności jest analogiczny do tego podanego wyżej, tzn NWD współczynników musi dzielić wyraz wolny - zatem w przypadku tego konkretnego układu musi być NWD(K,N)|X oraz NWD(K,N)|Y, co jest równoważne z warunkiem NWD(K,N)|NWD(X,Y).

Pozdrawiam.

[KaMyLuS]

Ok, tylko czy to wystarczy by UKŁAD był rozwiązywalny? Bo takie gdyby byly to rozlaczne rownania to OK wtedy kazde z osobna i git majonez. Ale tu mamy układ, że zmienne z 1szego rownania wystepuja w 2gim. Zatem czy w tej sytuacji nie mogloby sie zdarzyc tak, ze ten warunek rozwiazywalnosci kazdego z tych rownan nie wystarczy by stwierdzic rozwiazywalnosc calego UKLADU?

[BettyBoo]

No tak, teraz to ja się zagalopowałam, bo to warunek konieczny tylko, ale niewystarczający

Natomiast w przypadku tego konkretnego układu akurat, po dodaniu stronami i po odjęciu stronami otrzymujemy równoważny układ równań (to, że jest on równoważny z podanym układem wynika z tego, że przekształcenia elementarne nie zmieniają rozwiązań układu)
\(\displaystyle{ \begin{cases} (K+N)(a+c)=X+Y \\ (K-N)(b+d)=X-Y\end{cases}}\)
i stąd widać warunki rozwiązalności (tym razem WKW ) w postaci: (K+N)|(X+Y) oraz (K-N)|(X-Y).

Pozdrawiam.

[KaMyLuS]

Aby na pewno w tych przekształceniach jest wszystko dobrze?
\(\displaystyle{ K(a+b) + N(c+d)=X}\)
\(\displaystyle{ K(c-d) + N(a-b)=Y}\)
Niech w powyzszym oryginalnym rownaniu K = 2, N = 1, X = 2, Y = 2. Podstawiając to do Pani przekształceń mamy:
\(\displaystyle{ (2+1)(a+c)=2+2}\)
\(\displaystyle{ (2-1)(b+d)=2-2}\)
czyli
\(\displaystyle{ 3(a+c)=4}\)
\(\displaystyle{ b+d=0}\)
4 nie jest podzielne przez 3, wiec teoretycznie uklad nie powinien miec rozwiazan całkowitych. Ale okazuje się ze oryginalny (ktory powinien miec takie same rozw jak przekształcony) ma, np. a = c = d = 1, b = -1. ;] Zatem gdzies musi byc cos nie teges ;]

[BettyBoo]

Wszystko się zgadza z wyjątkiem tego, że nie umiem dodawać Oczywiście, po dodaniu i odjęciu stronami nie otrzymamy tego układu, który napisałam (poupraszczałam sobie współczynniki, które się nie upraszczają) - bo poza tym wszystko jest teges

Układu dla K=N=0 nie ma sensu rozpatrywać
Jeśli tylko N=0, to warunkiem rozwiązalności jest (K|X oraz K|Y) lub równoważnie K|NWD(X,Y)
Jeśli tylko K=0, to warunkiem rozwiązalności jest N|NWD(X,Y).
Te dwa warunki można zapisać jednym - jeśli któraś z liczb jest równa 0, to warunek ma postać NWD(K,N)|NWD(X,Y)

Resztę przemyślę jak się wyśpię
Pozdrawiam. I dobranoc.

====================================================
Wyspałam się i doszłam do wniosku, że chyba łatwiej będzie to częściowo rozwiązać, niż męczyć się na ogólnych wzorach. Może są jakieś ogólne warunki dotyczące rozwiązywalności układów równań diofantycznych, ale ja ich nie znam, więc umiem to zrobić tylko wprost. Przedstawię Ci najpierw genezę ostatecznego warunku - sprawdzaj, czy nie oszukuję

Zakładamy, że warunek konieczny zachodzi i rozwiązujemy pierwsze równanie (w oryginalnej postaci). W tym celu rozbijamy to równanie na układ 3 równań: \(\displaystyle{ \begin{cases} a+b=e\\ c+d=f\\ Ke+Nf=X\end{cases}}\)
Najpierw rozwiązujemy ostatnie równanie i mamy \(\displaystyle{ e=e_0+\frac{N}{NWD(K,N)}t,\ f=f_0-\frac{K}{NWD(K,N)}t,\ t\in\mathbb{Z}}\), gdzie \(\displaystyle{ e_0,f_0}\) jest dowolnym rozwiązaniem ostatniego równania (można je znaleźć na postawie rozszerzonego algorytmu Euklidesa).
Wobec tego mamy
\(\displaystyle{ \begin{cases} b=s\\ a=e-b=e_0+\frac{N}{NWD(K,N)}t-s \\ d=q\\ c=f-q= f_0-\frac{K}{NWD(K,N)}t-q\\ t,s,q\in\mathbb{Z}\end{cases}}\)
Wstawiamy to do drugiego równania i mamy \(\displaystyle{ N(e-2b)+K(f-2d)=Y}\), co po wymnożeniu i uporządkowaniu daje
\(\displaystyle{ \frac{N^2-K^2}{NWD(K,N)}t-2Ns-2Kq=Y-Ne_0-Kf_0}\).
Pytanie o to, czy istnieje rozwiązanie oryginalnego układu diofantycznego to pytanie o to, czy istnieją takie t,s,q, żeby powyższe równanie miało rozwiązanie - a więc teraz jesteśmy w domu

--------------------
Ostatecznie: Sprawdzamy najpierw czy jest spełniony warunek konieczny, tzn czy każde z równań ma rozwiązanie - jak pisałam kilka postów wyżej, ten warunek to \(\displaystyle{ NWD(K,N)|NWD(X,Y)}\). Jeśli on nie zachodzi, to nie ma rozwiązań, jeśli zachodzi, to warunkiem wystarczającym rozwiązalności jest np
\(\displaystyle{ NWD\left(\frac{N^2-K^2}{NWD(K,N)},2N,2K\right)\ | \ (Y-Ne_0-Kf_0)}\), przy czym \(\displaystyle{ Ke_0+Nf_0=X}\).

Ponieważ można otrzymać podobne warunki rozwiązując równanie 2 i wstawiając do 1, to być może podany wyżej warunek da się jakoś uprościć - możesz się nad tym zastanowić.
Pozdrawiam.