20051231, 13:23  #1 
Jun 2005
Near Beetlegeuse
110000100_{2} 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 20051231 at 13:27 
20051231, 13:39  #2 
Aug 2002
Buenos Aires, Argentina
2^{2}×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 20051231 at 13:47 
20051231, 15:18  #3  
Jun 2005
Near Beetlegeuse
2^{2}·97 Posts 
Thank you.
If I understand you correctly, then in the line: Quote:
Thank you. 

20051231, 19:22  #4 
Jun 2005
Near Beetlegeuse
2^{2}·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. 