Najmniejsza potęga, kongruencja z jedynką

[matinf]

Witam,

Mam takie pytanie:

Weźmy, że \(\displaystyle{ x}\) jest najmniejszą z liczb taką, że
\(\displaystyle{ a^x \equiv 1 (\mod n)}\)
To czy możemy wnioskować, że jeśli \(\displaystyle{ a^m \equiv 1 (\mod n)}\) to musi być, że \(\displaystyle{ m|x}\) ?

[Kaf]

Pierwsza uwaga: niech \(\displaystyle{ x}\) będzie najmniejszą dodatnią liczbą naturalną spełniającą ten warunek; druga: powinno być \(\displaystyle{ x|m}\) (dlaczego te warunki są konieczne/sensowne?).
Niech \(\displaystyle{ a^m \equiv 1 \pmod n}\). \(\displaystyle{ m}\) można przedstawić w postaci \(\displaystyle{ kx+r}\) przy powszechnie znanych założeniach (jakich?) na \(\displaystyle{ k}\) i \(\displaystyle{ r}\). Zatem \(\displaystyle{ 1 \equiv a^m \equiv a^{kx+r} \equiv a^r \pmod n}\). Teraz dokończ dowód

[matinf]

\(\displaystyle{ rin [0; x)}\)
No doszedłeś do wniosku, że:

\(\displaystyle{ 1 \equiv a^r (\mod n)}\)

Czyli teraz, żeby powiedzieć, że \(\displaystyle{ x|m}\) musi być, że \(\displaystyle{ r>0}\).

Ale wiemy, że \(\displaystyle{ x}\) jest minimalne oraz \(\displaystyle{ r}\) jest od niego mniejsze. Wobec tego musi być \(\displaystyle{ r=0}\)

[Ponewor]

Czyli teraz, żeby powiedzieć, że \(\displaystyle{ x|m}\) musi być, że \(\displaystyle{ r>0}\).

Czyżby?

[Kartezjusz]

Tak się dobieramy \(\displaystyle{ r}\)

[matinf]

Czyżby?

Miałem na myśli, równość

[Kaf]

Gdyby wyrzucić zdanie

Czyli teraz, żeby powiedzieć, że \(\displaystyle{ x|m}\) musi być, że \(\displaystyle{ r>0}\).

to rozumowanie jest poprawne.