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 ........$\Large \frac{6h-1}{p}=\{1, 5\}$ This is obviously connected to the fact that ........$\Large p=6q+r$ where $\Large r = \{1, 5\}$. So, if we start by assuming that $\Large \frac{6h-1}{6q+r}= 6-r$ then we get ...$\Large (6q+r)(6-r) = 6h-1$ ........$\Large 6q - qr + r - r^{2} = h -1$ Now, when $\Large r = 1$ I can simplify this to $\Large h = 5q+r$ but when $\Large r = 5$ 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 $\Large \frac{6h-1}{6q+r}=6-r$, and this left me with the unfortunate $\Large 6q-qr+r-r^{2}$. If we replace the denominator with the rather obvious $\Large p$ then instead we get the very simple $\Large 6p-pr$ 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.