Let p be a prime, and (x,p) = 1
If for integers a and b we have xa≡xb (mod p) for all x∈Z, show that a≡b (mod p−1)
I know that if xa≡1(mod p), then it implies that a≡0(mod p−1), but I don't know how to go from here.
Any tips would be appreciated!
Answer
Hint Let x=a be a primitive root, i.e. a has order p−1 Then it is the special case of (⇐) below where m=p and e=p−1 (by little Fermat).
Theorem Suppose that: ae≡1(modm) and e>0, n,k≥0 are integers. Then
n≡k(mode)⟹an≡ak(modm). Further, conversely
n≡k(mode)⟸an≡ak(modm) if a has order e mod m
Proof Wlog n≥k so an≡an−kak≡ak⟺an−k≡1, by cancelling ak using ae≡1⇒a is invertible so cancellable (cf. Remark). n≡k(mode)⟹ an−k≡1, and conversely if a has order e, by here,
Remark If you are familiar with modular inverses then it is not necessary to restrict to nonnegative powers of a above since ae≡1, e>0⇒ a is invertible by aae−1≡1 so a−1≡ae−1.
No comments:
Post a Comment