tag:blogger.com,1999:blog-6704226767646806218.post334761977813630538..comments2024-02-28T23:40:25.664-08:00Comments on Programming and Algorithms: Sieve Methods : Prime, Divisor, Euler Phi etc.praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-6704226767646806218.post-76637095757681764002013-05-26T22:18:48.269-07:002013-05-26T22:18:48.269-07:00I think some people could not figure out that from...I think some people could not figure out that from the article, may be it was not so clear enough. So I am telling it here again. <br /><br />See the lines from the above post.<br />"Now I will tell you another easier method . Generalized version of Fermat's theorem says that a ^ phi(m) = 1 mod m where gcd(a, m) = 1. Fir finding inverse a ^ (phi(m) - 1) = 1 / a (mod m) = (inverse(a)) mod m.<br /> Hence for finding inverse(a) mod m, You can just find a ^ (phi(m) - 1) by modular exponention method. In case of m being prime, As phi(m) = m - 1. So just find a ^ (m - 2) % m. This is what precisely computed by modpow function in the above function."<br /><br />So for finding inverse(a) when m is not prime, (note inverse exists only when gcd(a,m) = 1), use <br />the formula (a ^ (phi(m) - 1)) % m.<br />I have already told the method to calculate value of phi(m).<br /><br />I hope it helps :)praveendhinwahttps://www.blogger.com/profile/03892182821438710542noreply@blogger.comtag:blogger.com,1999:blog-6704226767646806218.post-48558912225384497972013-05-26T15:33:43.811-07:002013-05-26T15:33:43.811-07:00Hey Praveen,
How to find inverse modulo of...Hey Praveen,<br /> How to find inverse modulo of a number when MOD is not prime.<br /><br />for example ,how can I find (1/2)%6. Here, 6 is not prime, so I cant write inverse(2)=pow(2,6-2).........<br /><br />Please, help me out with this. Thank you..Anonymoushttps://www.blogger.com/profile/11264356452835593851noreply@blogger.com