mersenneforum.org modular arithmetic
 Register FAQ Search Today's Posts Mark Forums Read

2011-05-18, 17:28   #34
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by science_man_88 Wikipedia would lead me to believe this means that q^2 mod q = p using that search.
though other searching seems to point towards:

http://en.wikipedia.org/wiki/Multiplicative_order and solving for k=p for mod q and base a or what ever.

2011-05-18, 21:41   #35
jyb

Aug 2005
Seattle, WA

1,567 Posts

Quote:
 Originally Posted by science_man_88 I can't quite get what a order 2 modulo is ( I've google searched and still can't find a simple answer).
The (multiplicative) order of b modulo n (which I think is what you're asking about) is defined to be the least positive number k such that b^k == 1 (mod n). Here n and b are assumed to be coprime.

So for example, the order of 2 mod 7 is 3, since 2^3 == 1 (mod 7) and there is no smaller positive exponent for which that would be true. On the other hand, the order of 3 mod 7 is 6 (try looking at the powers of 3 mod 7 to verify this for yourself).

An important fact about multiplicative orders is that if b^k == 1 (mod n), then the order of b mod n must divide k. See if you can prove this for yourself. For example, 4^6 == 1 (mod 21), so the order of 4 mod 21 must divide 6. And indeed, you can check that it's 3.

2011-05-18, 21:44   #36
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by jyb The (multiplicative) order of b modulo n (which I think is what you're asking about) is defined to be the least positive number k such that b^k == 1 (mod n). Here n and b are assumed to be coprime. So for example, the order of 2 mod 7 is 3, since 2^3 == 1 (mod 7) and there is no smaller positive exponent for which that would be true. On the other hand, the order of 3 mod 7 is 6 (try looking at the powers of 3 mod 7 to verify this for yourself). An important fact about multiplicative orders is that if b^k == 1 (mod n), then the order of b mod n must divide k. See if you can prove this for yourself. For example, 4^6 == 1 (mod 21), so the order of 4 mod 21 must divide 6. And indeed, you can check that it's 3.
I'm asking more about the quote from the OEIS I made because I kinda want to find other relations other than the p=4k+3 and q=2p+1 situation the quote talks of. I don't get what it's talking of the multiplicative article I found on Wikipedia is the one that even makes sense to me but I'm likely wrong. I can't quite figure out the other articles suggested

Last fiddled with by science_man_88 on 2011-05-18 at 21:46

 2011-05-18, 23:42 #37 CRGreathouse     Aug 2006 134458 Posts sm: Try znorder(Mod(2,101)) and the like.
2011-05-19, 00:05   #38
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 Originally Posted by CRGreathouse sm: Try znorder(Mod(2,101)) and the like.
okay I see kinda what znorder does , the problem is I still don't see what the quoted material means.

 2011-07-22, 19:40 #39 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·131 Posts Lucas Lehmer test okay I'm back , this time about something I see that might drop a step in the LL test: is there a way to test to find y: IF $x \equiv 2 \text { mod p}$ then $\sqrt{x} \equiv \text {y mod p}$ if so we can take the LL test down one step , because if $S_{n}+2 \equiv 2 \text { mod p}$ then $S_{n-1} \equiv \text {y mod p}$
2011-07-22, 21:41   #40
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by science_man_88 okay I'm back , this time about something I see that might drop a step in the LL test: is there a way to test to find y: IF $x \equiv 2 \text { mod p}$ then $\sqrt{x} \equiv \text {y mod p}$ if so we can take the LL test down one step , because if $S_{n}+2 \equiv 2 \text { mod p}$ then $S_{n-1} \equiv \text {y mod p}$
I found :

http://mathforum.org/library/drmath/view/66757.html

if applied generally instead of just to 2 it might be able to get it back to the first $S_{n}\gt {M_{p}}$ would that speed things up ? though I'm kinda confused about what I found.

Last fiddled with by science_man_88 on 2011-07-22 at 21:42

 2011-07-23, 01:57 #41 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·131 Posts just realized something using PARI: Code: (22:43)>for(x=1,7,print((x^2)%7"::"x",")) 1::1, 4::2, 2::3, 2::4, 4::5, 1::6, 0::7, note how the x that have remainder 2 are 2^w and the mersenne-2^w this seems to work so far using 31 and 127 as well. so $S_{n-1} \equiv +/-2^w \text { mod the Mersenne chosen}$ and yes I know 2 possible remainders not 1. 2^w starts at w=2 and seems to work w up one every odd number after p=3. that's all I have for now.
2011-07-24, 01:09   #42
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 Originally Posted by science_man_88 just realized something using PARI: Code: (22:43)>for(x=1,7,print((x^2)%7"::"x",")) 1::1, 4::2, 2::3, 2::4, 4::5, 1::6, 0::7, note how the x that have remainder 2 are 2^w and the mersenne-2^w this seems to work so far using 31 and 127 as well. so $S_{n-1} \equiv +/-2^w \text { mod the Mersenne chosen}$ and yes I know 2 possible remainders not 1. 2^w starts at w=2 and seems to work w up one every odd number after p=3. that's all I have for now.
just realized something while rereading this post: $M_P=odd$ so they alternate I think the problem is for me to figure out which one it falls on.

2011-07-26, 02:02   #43
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by science_man_88 just realized something while rereading this post: $M_P=odd$ so they alternate I think the problem is for me to figure out which one it falls on.
figured out how to relate w back to p:

w=(p+1)/2 = ceil(p/2)

so can we use this to relate the next step to a mod p ?

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 1 2016-10-21 22:21 JuanTutors Math 4 2009-03-11 16:06 ixfd64 Programming 15 2008-07-30 03:52 Numbers Math 27 2005-11-30 15:41 ixfd64 Software 0 2004-05-27 05:42

All times are UTC. The time now is 22:32.

Wed Sep 30 22:32:26 UTC 2020 up 20 days, 19:43, 0 users, load averages: 1.72, 1.57, 1.50