Podaj warunki konieczne i wystarczające na x i c

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Rysio
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 20 paź 2017, o 23:43
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz

Podaj warunki konieczne i wystarczające na x i c

Post autor: Rysio » 20 paź 2017, o 23:55

Podaj warunki konieczne i wystarczające na \(\displaystyle{ x}\) i \(\displaystyle{ c}\), aby zachodziło: dla dowolnych \(\displaystyle{ a, b}\), jeśli \(\displaystyle{ ax \equiv bx \pmod{c}}\), to \(\displaystyle{ a \equiv b \pmod{c}}\).

Zrobiłem program komputerowy, który sprawdził mi to dla 1000 liczb i wniosek wynikł taki, że warunkiem koniecznym i wystarczającym jest to, by \(\displaystyle{ NWD(x, c) = 1}\).
Ale jak rozwiązać te zadanie w sposób matematyczny? Jak to zapisać i wyjaśnić?

Z góry dziękuję za pomoc
Rysio
Ostatnio zmieniony 21 paź 2017, o 15:44 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm . Temat umieszczony w złym dziale.

Awatar użytkownika
Igor V
Użytkownik
Użytkownik
Posty: 1605
Rejestracja: 16 lut 2011, o 16:48
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 18 razy
Pomógł: 604 razy

Podaj warunki konieczne i wystarczające na x i c

Post autor: Igor V » 21 paź 2017, o 01:24

\(\displaystyle{ ax \equiv bx \pmod{c} \Leftrightarrow \frac{ax - bx}{c} = l \in \ZZ}\)
Niech \(\displaystyle{ d = \NWD(x, c)}\). Dzieląc stronami mamy:
\(\displaystyle{ (a - b)\frac{x}{d} = l \frac{c}{d}}\)

Ponieważ \(\displaystyle{ \frac{x}{d}}\) jest względnie pierwsza z \(\displaystyle{ \frac{c}{d}}\) to jeśli lewa strona jest podzielna przez \(\displaystyle{ \frac{c}{d}}\) to musi \(\displaystyle{ \frac{c}{d}}\) dzielić \(\displaystyle{ a-b}\) ,czyli :
\(\displaystyle{ a \equiv b \pmod{c/d}}\)
Widać Twój przypadek szczególny dla \(\displaystyle{ \NWD(x, c) = 1}\)

ODPOWIEDZ