Rozwiązania kilku równań diofantycznych

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
matemix
Użytkownik
Użytkownik
Posty: 394
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 9 razy

Rozwiązania kilku równań diofantycznych

Post autor: matemix » 1 gru 2019, o 11:50

Szukam rozwiązań takich równań:

\(\displaystyle{ \frac {a^2}{8} + \frac {ab}{8} + \frac {b}{4} = x_{1}}\)

\(\displaystyle{ 3 \cdot \frac {a}{8} + \frac {b}{8} = x_{2}}\)

\(\displaystyle{ 5 \cdot \frac {a^3}{8} + \frac {a^2 \cdot b}{8} + \frac {ab}{4} + \frac {b}{2} = x_{3}}\)

\(\displaystyle{ 7 \cdot \frac {a^2}{8} + \frac {ab}{8} + \frac {b}{2} = x_{4}}\)

Wszystkie zmienne \(\displaystyle{ x_{i}}\) to liczby całkowite. Zaś liczby \(\displaystyle{ a}\) i \(\displaystyle{ b}\) też powinny być całkowite. Ale chyba nie ma liczb całkowitych \(\displaystyle{ a}\) i \(\displaystyle{ b}\), które spełniałyby to równanie (o ile dobrze mi się wydaje, nie wiem jak to wykazać)? Zastanawiam się zatem, czy istnieją jakieś rozwiązania w liczbach całkowitych zespolonych?
Ostatnio zmieniony 1 gru 2019, o 12:15 przez matemix, łącznie zmieniany 2 razy.

a4karo
Użytkownik
Użytkownik
Posty: 17394
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 4 razy
Pomógł: 2931 razy

Re: Rozwiązania kilku równań diofantycznych

Post autor: a4karo » 1 gru 2019, o 11:57

Dziwne zadanie:
wstaw za \(a,b\) dowolne liczby parzyste i wylicz \(x_i\)

matemix
Użytkownik
Użytkownik
Posty: 394
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 9 razy

Re: Rozwiązania kilku równań diofantycznych

Post autor: matemix » 1 gru 2019, o 12:20

Zrobiłem błąd, już poprawiłem. Teraz równanie wygląda nieco inaczej. Ale znalazłem rozwiązania:

\(\displaystyle{ a=-7}\)

\(\displaystyle{ b=-3}\)

Tyle, że metodą brute force. Jak rozwiązywać takie równania?

a4karo
Użytkownik
Użytkownik
Posty: 17394
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 4 razy
Pomógł: 2931 razy

Re: Rozwiązania kilku równań diofantycznych

Post autor: a4karo » 1 gru 2019, o 12:37

A co w tych równania jest niewiadomą?

matemix
Użytkownik
Użytkownik
Posty: 394
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 9 razy

Re: Rozwiązania kilku równań diofantycznych

Post autor: matemix » 1 gru 2019, o 12:59

Chcę znaleźć \(\displaystyle{ a}\) i \(\displaystyle{ b}\), one są niewiadomą i mają to być liczby nieparzyste. Liczby \(\displaystyle{ x_{i}}\) nie są dla mnie istotne, ale też są niewiadomymi.

Podobny problem mamy z takim układem równań:

\(\displaystyle{ \frac {a^3}{16} + \frac {a^2 \cdot b}{16} + \frac {ab}{8} + \frac {b}{2} = x_{1}}\)

\(\displaystyle{ 3 \cdot \frac {a^2}{16} + \frac {ab}{16} + \frac {b}{2}= x_{2}}\)

\(\displaystyle{ 5 \cdot \frac {a^4}{16} + \frac {a^3 \cdot b}{16} + \frac {a^2 \cdot b}{8} + \frac {ab}{4} + \frac {b}{2}= x_{3}}\)

\(\displaystyle{ 7 \cdot \frac {a^3}{16} + \frac {a^2 \cdot b}{16} + \frac {ab}{4} + \frac {b}{2}= x_{4}}\)

\(\displaystyle{ 9 \cdot \frac {a^2}{16} + \frac {ab}{16} + \frac {b}{8} = x_{5}}\)

\(\displaystyle{ 11 \cdot \frac {a}{16} + \frac {b}{16}= x_{6}}\)

\(\displaystyle{ 13 \cdot \frac {a^3}{16} + \frac {a^2 \cdot b}{16} + \frac {ab}{8} + \frac {b}{4}= x_{7}}\)

\(\displaystyle{ 15 \cdot \frac {a^2}{16} + \frac {ab}{16} + \frac {b}{4}= x_{8}}\)

Ale tutaj, o ile nie zrobiłem błędu (gdy wyliczałem równania) nie ma rozwiązań dla \(\displaystyle{ a}\) i \(\displaystyle{ b}\) całkowitych, nieparzystych. Dlatego myślałem o rozwiązaniach zespolonych. Ale nie wiem jak to rozwiązywać. Sprawdziłem tylko wszystkie wariacje z powtórzeniami \(\displaystyle{ a}\) i \(\displaystyle{ b}\) w zakresie od \(\displaystyle{ -15}\) do \(\displaystyle{ 15}\) (i wstawiałem po kolei do wzorów, patrząc, czy każde równanie da wynik całkowity, czy nie). Dla wybranych liczb \(\displaystyle{ a+16p}\) do \(\displaystyle{ b+16q}\) lewe strony równań, przemnożone przez \(\displaystyle{ 16}\) dają te same reszty z dzielenia modulo \(\displaystyle{ 16}\). Dlatego wystarczyło sprawdzić rozwiązania w tym zakresie. Pytanie czy są jakieś rozwiązania np. dla liczb zespolonych? Tylko tutaj nieparzystość chyba nie będzie istotna.

Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 230
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu
Podziękował: 29 razy
Pomógł: 36 razy

Re: Rozwiązania kilku równań diofantycznych

Post autor: Gosda » 1 gru 2019, o 14:19

Byłoby trochę prościej pomóc, gdybyś zdradził, skąd się te równania wzięły.

matemix
Użytkownik
Użytkownik
Posty: 394
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 9 razy

Re: Rozwiązania kilku równań diofantycznych

Post autor: matemix » 1 gru 2019, o 15:12

Jak wyjaśnię skąd się biorą te równania to raczej nie będzie prościej. Badam złożenia pewnych permutacji. Sposób generowania tych permutacji jest następujący - obliczamy funkcję rekurencyjną:

\(\displaystyle{ f(x) = \begin{cases} \frac {a}{2} \cdot x+ \frac {b}{2} &\text{dla } x - nieparzystych\\\frac {x}{2} &\text{dla } x - parzystych \end{cases}}\)

Dla dowolnych całkowitych \(\displaystyle{ a}\) oraz \(\displaystyle{ b}\). W ten sposób generujemy ciągi liczbowe. Na wejściu są kolejne liczby naturalne. Ciągi te obliczamy dla jakiejś liczby iteracji, przyjętej z góry (np. \(\displaystyle{ 4}\) iteracje) i przekształcamy w pewien sposób. Zamieniamy każdą liczbę nieparzystą w wygenerowanym ciągu na \(\displaystyle{ 1}\) a każdą parzystą na \(\displaystyle{ 0}\). I w ten sposób otrzymujemy pewną liczbę binarną. Ale odczytujemy ją odwrotnie, od najmniejszej potęgi dwójki z lewej, do największej. Jeżeli wykonamy takie obliczenia na przykład dla liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ 16}\), to otrzymamy pewną permutację. Konkretnie wziąłem dwie permutacje \(\displaystyle{ a=3}\), \(\displaystyle{ b=1}\) i \(\displaystyle{ a=3}\), \(\displaystyle{ b=-1}\). I pomnożyłem jedną razy drugą. Otrzymałem w wyniku tego trzecią permutację:

\(\displaystyle{ 11,6,9,12,15,2,13,8,3,14,1,4,7,10,5,0}\)

I teraz chcę ustalić jakie parametry \(\displaystyle{ a}\) i \(\displaystyle{ b}\) odpowiadają tej permutacji. Jakie wartości trzeba wstawić do funkcji, aby dostać dokładnie taką permutację. W celu ustalenia tego zapisałem te liczby binarnie (ale w odwróconej kolejności), na przykład \(\displaystyle{ 11}\) to \(\displaystyle{ 1101}\) i przyporządkowałem kolejnym jedynkom i zerom odpowiadającą im operację. Jeśli jakieś \(\displaystyle{ a}\) i \(\displaystyle{ b}\) dają taką permutację, to dla liczby jeden w takim ciągu rekurencyjnym musi zachodzić mnożenie, mnożenie, dzielenie, mnożenie i dać na wyjściu jakąś liczbę całkowitą. Dokładnie to jest zapisane w pierwszym równaniu. Równania napisałem tylko dla liczb nieparzystych, bo wydaje mi się, że można to tak uprościć i, jeśli znajdzie się rozwiązanie dla liczb nieparzystych, to będzie się zgadzać także dla parzystych.

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3806
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 89 razy
Pomógł: 369 razy

Re: Rozwiązania kilku równań diofantycznych

Post autor: arek1357 » 1 gru 2019, o 22:28

dla:

\(\displaystyle{ a=3 , b=1}\)

\(\displaystyle{ f(3)=5 , f(5)=8 , f(8)=4 , f4)=2 , f(2)=1, f(1)=2}\)

\(\displaystyle{ (3,5,8,4,2,1,2)}\)

Co to za permutacja albo czegoś nie rozumiem?...

matemix
Użytkownik
Użytkownik
Posty: 394
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 9 razy

Re: Rozwiązania kilku równań diofantycznych

Post autor: matemix » 2 gru 2019, o 18:29

Permutacja dla \(\displaystyle{ a=3}\) i \(\displaystyle{ b=1}\), dla \(\displaystyle{ 4}\) iteracji, dla zakresu liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ 16}\), to:

\(\displaystyle{ (5,10,3,4,1,6,7,8,13,2,11,12,9,14,15,0)}\)

Ponieważ ciąg:

\(\displaystyle{ f(x) = \begin{cases} \frac {3}{2} \cdot x+ \frac {1}{2} &\text{dla } x - nieparzystych\\\frac {x}{2} &\text{dla } x - parzystych \end{cases}}\)

Dla liczby \(\displaystyle{ 1}\) wygląda tak:

\(\displaystyle{ 2,1,2,1}\)

Po zamianie na zera i jedynki mamy:

\(\displaystyle{ 1,0,1,0}\)

Co daje liczbę:

\(\displaystyle{ 2^0 \cdot 1 + 2^1 \cdot 0 + 2^2 \cdot 1 + 2^3 \cdot 0 = 5}\)

Tak naprawdę liczbę zamieniamy na \(\displaystyle{ 1}\) w zapisie binarnym, gdy była wykonana operacja typu \(\displaystyle{ \frac {3}{2} \cdot x + \frac {1}{2}}\), a gdy dzielenie przez \(\displaystyle{ 2}\), to zamieniamy liczbę na zero. W poprzednim poście źle się wyraziłem. Możemy pozamieniać równie dobrze wszystkie liczby nieparzyste na \(\displaystyle{ 1}\), jeśli za pierwszą iterację uznamy już zaimplementowanie liczby i wtedy obliczenia według funkcji rekurencyjnej wykonujemy tylko \(\displaystyle{ 3}\), ale dostajemy i tak liczbę o \(\displaystyle{ 4}\) bitach. Ale może lepiej pozostać przy zasadzie zamienia liczby na jeden lub zero, w zależności do tego czy było wykonane mnożenie, czy dzielenie. Idąc dalej na przykład element \(\displaystyle{ 13}\) permutacji będzie obliczony tak:

\(\displaystyle{ 20,10,5,8}\)

co daje:

\(\displaystyle{ 1,0,0,1 = 9}\)

Tak samo permutację wyznaczyłem dla \(\displaystyle{ a=3}\) i \(\displaystyle{ b=-1}\), wynosi ona:

\(\displaystyle{ (15,14,9,12,11,2,13,8,7,6,1,4,3,10,5,0)}\)

I pomnożyłem jedną razy drugą. Otrzymałem:

\(\displaystyle{ (11,6,9,12,15,2,13,8,3,14,1,4,7,10,5,0)}\)

Liczyłem, że znajdę jakieś parametry \(\displaystyle{ a}\) i \(\displaystyle{ b}\), dla których wyznaczę permutację w ten sam sposób i będzie odpowiadała wynikowi mnożenia. W ogóle próbuję zrozumieć zasady tego mnożenia i jaka logika za tym stoi. Tj. chciałbym umieć mając tylko parametry \(\displaystyle{ a}\) i \(\displaystyle{ b}\) umieć wyznaczyć wynik mnożenia dwóch permutacji, również zapisany jako \(\displaystyle{ a}\) i \(\displaystyle{ b}\), bez rozpisywania całych permutacji. Nie wiem jednak, czy istnieje w tym jakaś logika.

ODPOWIEDZ