mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-12-31, 13:23   #1
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

1100001002 Posts
Default 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
Numbers is offline   Reply With Quote
Old 2005-12-31, 13:39   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22×3×113 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2005-12-31, 15:18   #3
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22·97 Posts
Default

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 is offline   Reply With Quote
Old 2005-12-31, 19:22   #4
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22·97 Posts
Default

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.
Numbers is offline   Reply With Quote
Reply

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.