rozwiąż kongruencję:
\(\displaystyle{ (a + b) \cdot x \equiv a^2 + b^2 (mod \ ab)}\) gdzie \(\displaystyle{ NWD(a,b) = 1}\).
Będę wdzięczny za jakąkolwiek wskazówkę.
rozwiąż kongruencję
-
- Użytkownik
- Posty: 5
- Rejestracja: 17 maja 2010, o 21:09
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 1 raz
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
rozwiąż kongruencję
Po pomnożeniu stronami przez \(\displaystyle{ a+b}\) dostaniemy:
\(\displaystyle{ (a^2 + b^2) \cdot x \equiv (a^2 + b^2)(a+b) \mod ab}\)
co wobec \(\displaystyle{ NWD(a^2+b^2,ab)=1}\) oznacza, że
\(\displaystyle{ x \equiv (a+b) \mod ab}\)
Q.
\(\displaystyle{ (a^2 + b^2) \cdot x \equiv (a^2 + b^2)(a+b) \mod ab}\)
co wobec \(\displaystyle{ NWD(a^2+b^2,ab)=1}\) oznacza, że
\(\displaystyle{ x \equiv (a+b) \mod ab}\)
Q.
-
- Użytkownik
- Posty: 5
- Rejestracja: 17 maja 2010, o 21:09
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 1 raz
rozwiąż kongruencję
Po pomnożeniu stronami wg mnie byłoby tak:
\(\displaystyle{ (a + b)^2 \cdot x \equiv (a^2 + b^2)(a+b) \mod ab}\)
i jak ma na podstawie \(\displaystyle{ NWD(a,b) = 1}\) dojść do \(\displaystyle{ NWD(a^2+b^2,ab)=1}\) ?
\(\displaystyle{ (a + b)^2 \cdot x \equiv (a^2 + b^2)(a+b) \mod ab}\)
i jak ma na podstawie \(\displaystyle{ NWD(a,b) = 1}\) dojść do \(\displaystyle{ NWD(a^2+b^2,ab)=1}\) ?
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
rozwiąż kongruencję
Po pierwsze:
\(\displaystyle{ (a+b)^2=a^2+b^2+2ab \equiv a^2+b^2 \mod ab}\)
Po drugie:
Załóżmy, że \(\displaystyle{ NWD (a^2+b^2,ab) =d>1}\). W szczególności oznacza to, że \(\displaystyle{ d |ab}\), więc \(\displaystyle{ d}\) dzieli dokładnie jedną z liczb \(\displaystyle{ a,b}\) (bo są one względnie pierwsze). Załóżmy, że jest to \(\displaystyle{ a}\). Wówczas musiałoby być też \(\displaystyle{ d| [(a^2+b^2)-a^2]}\) (bo różnica liczb podzielnych przez \(\displaystyle{ d}\) też jest podzielna przez \(\displaystyle{ d}\). Ale to już jest sprzeczność.
Q.
\(\displaystyle{ (a+b)^2=a^2+b^2+2ab \equiv a^2+b^2 \mod ab}\)
Po drugie:
Załóżmy, że \(\displaystyle{ NWD (a^2+b^2,ab) =d>1}\). W szczególności oznacza to, że \(\displaystyle{ d |ab}\), więc \(\displaystyle{ d}\) dzieli dokładnie jedną z liczb \(\displaystyle{ a,b}\) (bo są one względnie pierwsze). Załóżmy, że jest to \(\displaystyle{ a}\). Wówczas musiałoby być też \(\displaystyle{ d| [(a^2+b^2)-a^2]}\) (bo różnica liczb podzielnych przez \(\displaystyle{ d}\) też jest podzielna przez \(\displaystyle{ d}\). Ale to już jest sprzeczność.
Q.
-
- Użytkownik
- Posty: 5
- Rejestracja: 17 maja 2010, o 21:09
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 1 raz