mersenneforum.org > Math Inv(6) in Z/p*
 User Name Remember Me? Password
 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.

 Thread Tools

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.