Hello, freinds recently i was confronted with a problem which goes like this->
Given a positive odd prime number p and another positive integer k (1<k<=p-1) find the minimum value of m such that pow(k,m)%p=1.
One straight way of approaching this is to iterate untill we get what we need thus contributing a time complexity of O(p), but i fancy if there exists even a more efficient way to do so. Can anyone help me or give some clue of how to solve it in less than O(p) time complexity.
Although it now seems to me that it has to don something with euler tuoteint function but couldn't figure it out! xD.
iterate over divisors of phi(p).
I tried it over few samples and found it correct. Will you please explain the logic behind it?
modular powers are perodic with period phi(p).if there exist a period smaller than phi(p) than, phi(p) must be multiple of that period.
claim: $$$m=p-1$$$. If possible let there exist smallest $$$r<p-1$$$ s.t. $$$k^r \equiv 1\,mod\,p.$$$ Since $$$p>r$$$ so $$$p=rq+r_1 \,\, ,r_1<r$$$ for some integer $$$q$$$. Now $$$k^{p-1} \equiv k^{rq+r_1-1} \equiv k^{r_1-1} \equiv 1\, mod\, p. (k^{p-1} \equiv 1\,mod\,p)$$$(by LFT) so we got a contradiction that r was smallest since we found $$$r_1-1<r$$$. Hence $$$m=p-1$$$
It is not always true. For example, if p=5 and k=4 then by your logic it should be m=5-1=4. Though pow(4,4)%5=1, but for m=2 also pow(4,2)%5=16%5=1. Hence , the right answer would then be 2 and not 4.
Oh I write that to find mistake in my proof. Now I got it you should ask minimum positive m (otherwise m=0 always work) and in my proof part mistake is r1-1 should not be equal to 0 then only that proof is correct otherwise not. Thanks btw.