Wyznacz liczbę k z podanej kongruencji

[mariolka0303]

Jak wyznaczyć \(\displaystyle{ k}\) z następującej kongruencji: \(\displaystyle{ 2^{k} \equiv 1(mod11)}\)?

[Vax]

Zauważ, że \(\displaystyle{ 2}\) jest generatorem w \(\displaystyle{ \mathbb{Z}_{11}}\), tj \(\displaystyle{ ord_2(11) = 10}\), stąd \(\displaystyle{ 2^k \equiv 2^0 \pmod{11} \iff k \equiv 0\pmod{10}}\).

[vpprof]

Można też zastosować twierdzenie Eulera, które mówi, że jeśli \(\displaystyle{ a}\) oraz \(\displaystyle{ n}\) są względnie pierwsze, to \(\displaystyle{ a ^{\phi(n)} \equiv_n 1}\), gdzie \(\displaystyle{ \phi(n)}\) jest liczbą liczb względnie pierwszych z \(\displaystyle{ n}\). Tak więc \(\displaystyle{ 2^{10} \equiv_{11} 1}\). Skoro tak, to możemy podnieść lewą stronę do dowolnej potęgi, a prawa pozostanie ta sama.

[Vax]

vpprof, ale nie wiemy czy \(\displaystyle{ k = \phi(11)}\) jest najmniejszą liczbą naturalną taką, że \(\displaystyle{ 2^{k} \equiv 1\pmod{11}}\), czyli inaczej mówiąc czy \(\displaystyle{ \phi(11)}\) jest rzędem \(\displaystyle{ 2 \pmod{11}}\). Trzeba jeszcze sprawdzić dzielniki \(\displaystyle{ \phi(11)}\).

Żeby lepiej to zobrazować popatrz na taki przykład:

\(\displaystyle{ 2^k \equiv 1 \pmod{17}}\)

Z twierdzenia Eulera mamy po prostu \(\displaystyle{ 2^{16} \equiv 1\pmod{17}}\), jednak odpowiedź \(\displaystyle{ k \equiv 0\pmod{16}}\) jest błędna. Zauważ, że \(\displaystyle{ ord_2(17) = 8}\), tj \(\displaystyle{ 2^8 \equiv 1\pmod{17}}\) i \(\displaystyle{ 8}\) jest najmniejszą taką wartością naturalną. Stąd odpowiedzią jest \(\displaystyle{ k \equiv 0\pmod{8}}\).