rozwiąż kongruencję

[pastorczyk]

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ę.

[Qń]

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.

[pastorczyk]

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}\) ?

[Qń]

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.

[pastorczyk]

Tak jest, wszystko się zgadza. Serdecznie dzięki.