Inv(6) in Z/p*

Numbers · 2005-12-31, 13:23

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.

alpertron · 2005-12-31, 13:39

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.

Numbers · 2005-12-31, 15:18

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.

Numbers · 2005-12-31, 19:22

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.

2005-12-31, 13:23	#1
Numbers Jun 2005 Near Beetlegeuse 2²·97 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 2×683 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, 19:22	#4
Numbers Jun 2005 Near Beetlegeuse 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 $\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.