 mersenneforum.org > Math Inv(6) in Z/p*
 Register FAQ Search Today's Posts Mark Forums Read 2005-12-31, 13:23 #1 Numbers   Jun 2005 Near Beetlegeuse 1100001002 Posts Inv(6) in Z/p* Let's say Inv(6) in Z/p* = h In trying to calculate h for a range of p I noticed that ........ This is obviously connected to the fact that ........ where . So, if we start by assuming that then we get ... ........ Now, when I can simplify this to but when I can't get the algebra to work which makes me suspect that either my original assumption is incorrect or I have gone wrong somewhere. Any ideas. Last fiddled with by Numbers on 2005-12-31 at 13:27   2005-12-31, 13:39 #2 alpertron   Aug 2002 Buenos Aires, Argentina 22×3×113 Posts If h is the inverse of 6 modulo p=6k+r, from the definition of inverse we get: 6h - 1 = sp = s(6k + r) Operating modulo 6: 5 = sr (mod 6) So when p has the form 6k+1, the quotient is 5, and when p has the form 6k+5, the quotient is 1. Notice that 0 <= 6h - 1 < 6p so 0 <= s < 6. This means that the quotient cannot have other values that the ones shown in the previous paragraph. Last fiddled with by alpertron on 2005-12-31 at 13:47   2005-12-31, 15:18   #3
Numbers

Jun 2005
Near Beetlegeuse

22·97 Posts Thank you.

If I understand you correctly, then in the line:
Quote:
 Originally Posted by Alpertron 5 = sr (mod 6)
the 5 is modulus -1. So that in the general case we can say that m-1 = sr(mod m), and in the specific case of the primes where r = {1, 5}, sr always = 5.

Thank you.   2005-12-31, 19:22 #4 Numbers   Jun 2005 Near Beetlegeuse 22·97 Posts I got it! I just couldn't figure out why the algebra didn't work, and now I know. In my first post I wrote that , and this left me with the unfortunate . If we replace the denominator with the rather obvious then instead we get the very simple which works for both cases. And this has to be a whole lot easier than trying to implement the Extended Euclidean Algorithm, so I'm as happy as Larry. Thanks for your help.  Thread Tools Show Printable Version Email this Page

All times are UTC. The time now is 17:53.

Tue May 11 17:53:58 UTC 2021 up 33 days, 12:34, 1 user, load averages: 2.63, 2.68, 2.89