Sign in to follow this  
erlang

pangkat membagi $p-1$

Recommended Posts

Diberikan $p$ sebuah bilangan prima dan $d\in\mathbb{Z}$ sedemikian sehingga $d|p-1$. Buktikan ada tepat $d$ buah solusi bulat $0<x<p$ sehingga $x^d-1\equiv 0 \mod p$

Edited by sayakalah

Share this post


Link to post
Share on other sites

Perhatikan bahwa grup multiplikatif $\mathbb{Z}_p^{*}$  adalah grup siklis, maka terdapat generator (yang sebenarnya adalah primitive root) katakanlah $a$, sehingga $a^i$ berbeda semua modulo $p$, untuk $i=1,\cdots, p-1$, in particular  $a^j\not\equiv  1 \pmod p$ untuk $0<j<p-1$.  Jika $d=1$, maka $x=a^{p-1}$ adalah solusi dari persamaan pada soal, dan apabila ada solusi lain katakanlah $t<p$, maka $t \equiv a^j \pmod p$, diperoleh $a^{p-1} \equiv t \equiv a^j \pmod p$, atau $a^{p-1-j} \equiv 0 \pmod p$, sedangkan $0<p-1-j < p-1$ kontradiksi dengan $a$ primitive root.

 

Sekarang misalkan $d>1$, dan definisikan $\theta=\frac{p-1}{d}$ dan $s=a^{\theta}$, karena $0<\theta < p-1$ maka  $a^{\theta} \not \equiv 1 \pmod p$, perhatikan bahwa

 

\[x \in \{s, s^2, \cdots, s^{d}\}  \Rightarrow x^d \equiv a^{\theta d} \equiv 1 \pmod p \]

 

dan apabila $s^i \equiv s^{j}$ untuk $d\geq i>j \geq 1$, maka $s^{i-j} \equiv 1 \pmod p$ jadi $a^{\frac{(p-1)(i-j)}{d}} \equiv 1 \pmod p$, dan karena $i-j < d$, maka ini kontradiksi dengan $a$ sebagai primitif root. 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this