🚀 go-pugleaf

Julek pisze:
> Witam,
> znamy liczby naturalne a,b,w .
> Jak określić, czy istnieją takie liczby naturalne x,y, żeby była
> spełniona równość:
> ax+by=w
> ?
> 
> Z góry dzięki!
Jesteś pewien, że chodzi o liczby naturalne x, y a nie o całkowite? Ale
tak czy owak, załóżmy, że chodzi o całkowite. Potem możesz sprawdzić czy
mogą być naturalne badając znaki liczb. Znajdujesz c=NWD(a,b). w musi
dzielić się przez c. Inaczej nie ma takich liczb. Jeśli się dzieli to
takie liczby całkowite x,y istnieją, co więcej jest ich nieskończenie
wiele. Pomijam przypadki szczególne. Dla zabawy proponuję udowodnienie
następującego twierdzenia:
ALL a in Z\{0}. ALL b in Z\{0} NWD(a,b)=1 => EX x in Z. EX y in Z. ax+by=1

Inaczej mówiąc dla dowolnych dwóch liczb całkowitych a,b różnych od zera
 NWD(a,b)=1 implikuje, że istnieją dwie liczby całkowite x,y takie, że
ax+by=1.

Z powyższego wynika już szukane twierdzenie.

P.S. Mam nadzieję, że nic nie pomyliłem, jeśli tak to poprawcie.

Mateusz Grotek pisze:
> Julek pisze:
>> Witam,
>> znamy liczby naturalne a,b,w .
>> Jak określić, czy istnieją takie liczby naturalne x,y, żeby była
>> spełniona równość:
>> ax+by=w
>> ?
>>
>> Z góry dzięki!
> Jesteś pewien, że chodzi o liczby naturalne x, y a nie o całkowite? Ale
...

> 
> Inaczej mówiąc dla dowolnych dwóch liczb całkowitych a,b różnych od zera
>  NWD(a,b)=1 implikuje, że istnieją dwie liczby całkowite x,y takie, że
> ax+by=1.
> 
> Z powyższego wynika już szukane twierdzenie.
> 

rozwiązania szukaj w okolicach algorytmu Euklidesa.

On Sep 2, 5:06 am, Julek <julek...@go2.pl> wrote:

> znamy liczby naturalne a,b,w .
> Jak określić, czy istnieją takie liczby naturalne x,y, żeby była
> spełniona równość:
> ax+by=w
> ?

Skoro mówisz o **naturalnych**  x y,
to otrzymujesz skończoną liczbę możliwości.
Więc sprawdź je. Algorytm będzie szybki.
Całkiem naiwny algorytm, ale ciupinkę
przy nim pomyśl, żeby się czasem nie wygłupić :-)

Powodzenia,

    Wlodek