Liczby o pewnej własności - czy jest najmniejsza ?

[matinf]

Niech \(\displaystyle{ n = 100}\). Czy \(\displaystyle{ \phi(n)}\) to najmniejsza liczba \(\displaystyle{ \lambda}\) o tej własności, że jeśli \(\displaystyle{ a}\) jest względnie pierwsze z \(\displaystyle{ n}\), to \(\displaystyle{ a^{\lambda}\equiv 1(\mod n)}\)? Uogólnij tę obserwację.

Więc sprawa wygląda tak:

\(\displaystyle{ \phi(100) = 40}\).
W takim razie mamy, że \(\displaystyle{ a^{40} \equiv 1 (\mod 100)}\). Ale niekoniecznie jest to najmniejsza liczba o tej własności.
Możemy rozważyć każdy dzielnik liczby \(\displaystyle{ 40:\ \{2,4,5,8,10,20\}}\). Każda z tych liczb jest kandydatem, ale nie ma innego kandydata.

Z uogólnieniem nie wiem o co chodzi ? Jest na pewno jasne, że gdy \(\displaystyle{ \phi(n)}\) jest liczbą pierwszą to faktycznie jest to najmniejsza liczba o tej własności. Ale inne "lepsze" uogólnienie ?

[Zordon]

Jeśli \(\displaystyle{ n=p_1^{a_1}\cdot...\cdot p_k^{a_k}}\), to najmniejszą liczbą o własności powyżej jest \(\displaystyle{ \lambda(n)=NWW(\phi(p_1^{a_1}),..., \phi(p_k^{a_k}))}\)
Tymczasem \(\displaystyle{ \phi(n)=\phi(p_1^{a_1})\cdot ...\cdot \phi(p_k^{a_k})}\).
Kiedy jest równość pomiędzy \(\displaystyle{ \lambda(n)}\) i \(\displaystyle{ \phi(n)}\) można dość łatwo stwierdzić.

[matinf]

Niech \(\displaystyle{ n = 100}\). Czy \(\displaystyle{ \phi(n)}\) to najmniejsza liczba \(\displaystyle{ \lambda}\) o tej własności, że jeśli \(\displaystyle{ a}\) jest względnie pierwsze z \(\displaystyle{ n}\), to \(\displaystyle{ a^{\lambda}\equiv 1(\mod n)}\)? Uogólnij tę obserwację.

Więc sprawa wygląda tak:

\(\displaystyle{ \phi(100) = 40}\).
W takim razie mamy, że \(\displaystyle{ a^{40} \equiv 1 (\mod 100)}\). Ale niekoniecznie jest to najmniejsza liczba o tej własności.
Możemy rozważyć każdy dzielnik liczby \(\displaystyle{ 40:\ \{2,4,5,8,10,20\}}\). Każda z tych liczb jest kandydatem, ale nie ma innego kandydata.

Czy do tej pory dobrze wnioskuję ?

Co do Twojej odpowiedzi. Tak to rzeczywiście prawda jest.
No zachodzi równość wtedy gdy:
\(\displaystyle{ \phi(p_1^{a_1}), ... , \phi(p_k^{a_k})}\) są parami względnie pierwsze.

[Zordon]

Dobrze wnioskujesz, ale można powiedzieć więcej, \(\displaystyle{ \lambda(100)=20}\) i to miałeś właśnie zauważyć w tym zadaniu.

Co do Twojej odpowiedzi. Tak to rzeczywiście prawda jest.
No zachodzi równość wtedy gdy:
\(\displaystyle{ \phi(p_1^{a_1}), ... , \phi(p_k^{a_k})}\) są parami względnie pierwsze.

Tak, ale można powiedzieć więcej. Zauważ, że \(\displaystyle{ \phi(n)}\) jest na ogół liczbą parzystą...

[matinf]

Dobrze wnioskujesz, ale można powiedzieć więcej, \(\displaystyle{ \lambda(100)=20}\) i to miałeś właśnie zauważyć w tym zadaniu.

No tak, to z tego "nww".
Oczywiście mogę powiedzieć: Każda liczba \(\displaystyle{ x}\), która ma spełniać:
\(\displaystyle{ a^x \equiv 1 (\mod n)}\) musi być krotnością \(\displaystyle{ \lambda(n)}\) (pamiętam o tym, że a jest wzg. pierwsze z n).

Tak, ale można powiedzieć więcej. Zauważ, że \(\displaystyle{ \phi(n)}\) jest na ogół liczbą parzystą...

Wszystko to prawda. Ale co mi to mówi więcej ? Że liczba ta na ogół będzie parzysta ? O to Ci chodzi ?

[Zordon]

Nie, nie o to. Dwie liczby parzyste nie są względnie pierwsze.

[matinf]

No więc w takim razie o co ?

Jest jasne, że \(\displaystyle{ \phi(n)}\) jest prawie zawsze parzyste. Kiedy będzie to równe wartości: \(\displaystyle{ nww(\phi(p_1^{\alpha_1}), ...., \phi(p_k^{\alpha_k}))}\)

I dalej jedyne co mi przychodzi do głowy to to, że \(\displaystyle{ \phi(p_1^{\alpha_1}), ...., \phi(p_k^{\alpha_k})}\) muszą być parami względnie pierwsze. Ty chcesz dorzucić do tego jakąś dodatkową informację, ale jaką  ?

[Zordon]

Pytanie jest "kiedy są parami względnie pierwsze"?

[matinf]

No jak dodam do tego wszystkiego parzystość, to:
\(\displaystyle{ n > 2 \Rightarrow 2| \phi(n)}\)
\(\displaystyle{ \phi(p_1^{\alpha_1}), ...., \phi(p_k^{\alpha_k})}\)
Przyjrzyjmy się argumentom. Powiedzmy, że mamy TYLKO trzy takie "fi". I twierdzę, że przegraliśmy, nie ma równości.
Co najmniej dwie te "fi" mają liczby większe od dwójki jako argumenty, a więc są parzyste, a więc nie są względnie pierwsze. Gdy są dwa fi - jeden z argumentów musi być dwójką, a drugi byle czym - w przeciwnym razie przegraliśmy.
Jeśli jest jedno fi, to wygraliśmy, jest równość.

Czyli wniosek jest taki, że skrajnie rzadko zajdzie ta równość, zajdzie wtw gdy:
Liczba, która trafia pod fi, a więc modulnik jest potęgą liczby pierwszej.
Są dwie liczby fi, przy czym do jednej z nich trafia dwójka.

W przeciwnym razie nie zachodzi równość.

Teraz ?

[Zordon]

Zgadza się. Pewnie pozostaje Ci udowodnić ten wzór z mojego pierwszego posta.