Friday, 5 August 2016

number theory - Special Congruence Proof




Let p be a prime, and (x,p) = 1



If for integers a and b we have xaxb (mod p) for all xZ, show that ab (mod p1)





I know that if xa1(mod p), then it implies that a0(mod p1), 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 p1 Then it is the special case of () below where m=p and e=p1 (by little Fermat).



Theorem    Suppose that:  ae1(modm)  and e>0, n,k0 are integers. Then



nk(mode)anak(modm).  Further, conversely




nk(mode)anak(modm)  if a has order e mod m



Proof   Wlog nk so anankakakank1, by cancelling ak using ae1a is invertible so cancellable (cf. Remark). nk(mode) ank1, 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 ae1, e>0 a is invertible by aae11 so a1ae1.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...