 mersenneforum.org modular arithmetic
 Register FAQ Search Today's Posts Mark Forums Read  2011-03-31, 15:22   #23
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts Quote:
 Originally Posted by CRGreathouse No. (3^3)%8 = 3, and 4 >= 3, but (3^4)%8 ≠ 3.
Okay thanks I now think I know how to correct it to get a general principle. it depends on a-1 I believe for the first a that works .

the reason I saw this is 1 = (2-1) I tested it on 3^5 and it appears to work. so they will have gaps of a1-1 to work.   2011-03-31, 16:01   #24
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts Quote:
 Originally Posted by science_man_88 Okay thanks I now think I know how to correct it to get a general principle. it depends on a-1 I believe for the first a that works . the reason I saw this is 1 = (2-1) I tested it on 3^5 and it appears to work. so they will have gaps of a1-1 to work.
I actually know a bit of how to prove this just not in a way most would care for.   2011-03-31, 16:05   #25
CRGreathouse

Aug 2006

3·52·79 Posts Quote:
 Originally Posted by science_man_88 Okay thanks I now think I know how to correct it to get a general principle. it depends on a-1 I believe for the first a that works .
The general setting is where x is an element of an an arbitrary monoid such that x^a = x for some integer a > 1. In that case you can reduce exponents mod a-1, except that you can't assume that x^(k(a-1)) = 1 but rather x^(a-1). So x^(3a) = x^3 but x^(3a - 3) = x^(a-1). (It may be true that x^(a-1) = 1, but you can't prove it.)

Working with integers mod m, I think that if x^a = x and x is nonzero (that is, not divisible by m) then you can conclude that x^(a-1) = 1 (mod m). Can someone confirm? I'm a little sick and my mind is hazy today.   2011-03-31, 16:10   #26
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts Quote:
 Originally Posted by CRGreathouse The general setting is where x is an element of an an arbitrary monoid such that x^a = x for some integer a > 1. In that case you can reduce exponents mod a-1, except that you can't assume that x^(k(a-1)) = 1 but rather x^(a-1). So x^(3a) = x^3 but x^(3a - 3) = x^(a-1). (It may be true that x^(a-1) = 1, but you can't prove it.) Working with integers mod m, I think that if x^a = x and x is nonzero (that is, not divisible by m) then you can conclude that x^(a-1) = 1 (mod m). Can someone confirm? I'm a little sick and my mind is hazy today.
this is how it goes: we have already proved that x^a%z = x what we need to do is figure out the gap. such that x becomes x^a again, since we have 1 x already it takes a-1 exponents to line up again there fore if we find an a>1 for which this is true we know that x^(a+((a-1)*b)) will always have this property.

Last fiddled with by science_man_88 on 2011-03-31 at 16:20   2011-03-31, 17:24   #27
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by CRGreathouse The general setting is where x is an element of an an arbitrary monoid such that x^a = x for some integer a > 1. In that case you can reduce exponents mod a-1, except that you can't assume that x^(k(a-1)) = 1 but rather x^(a-1). So x^(3a) = x^3 but x^(3a - 3) = x^(a-1). (It may be true that x^(a-1) = 1, but you can't prove it.) Working with integers mod m, I think that if x^a = x and x is nonzero (that is, not divisible by m) then you can conclude that x^(a-1) = 1 (mod m). Can someone confirm? I'm a little sick and my mind is hazy today.
well if my math logic holds then I can confirm on the basis of:

x^(a-1)%z = ((x^a)%z)/x assuming ((x^a)%z) = x you would be correct as x/x = 1 for non 0 values of x.

Last fiddled with by science_man_88 on 2011-03-31 at 17:27   2011-03-31, 18:26   #28
R.D. Silverman

Nov 2003

746010 Posts Quote:
 Originally Posted by CRGreathouse Working with integers mod m, I think that if x^a = x and x is nonzero (that is, not divisible by m) then you can conclude that x^(a-1) = 1 (mod m). Can someone confirm? I'm a little sick and my mind is hazy today.
5^3 = 5 mod 10, but 5^2 != 1 mod 10. It isn't sufficient that
x is not divisible by m (5 is not divisible by 10). You need (x,m) = 1.   2011-03-31, 18:40 #29 CRGreathouse   Aug 2006 3×52×79 Posts Right, of course. I can't see or think straight today...   2011-03-31, 20:42   #30
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by CRGreathouse Right, of course. I can't see or think straight today...
CRG don't worry for the thinking part I'm like that every day.   2011-05-18, 15:42   #31
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts Quote:
 The (prime) number p appears in this sequence if and only if there is no prime q<2^p-1 such that the order of 2 modulo q equals p; a special case is that if p=4k+3 is prime and also q=2p+1 is prime then the order of 2 modulo q is p so p is not a term of this sequence.
I can't quite get what a order 2 modulo is ( I've google searched and still can't find a simple answer).

Last fiddled with by science_man_88 on 2011-05-18 at 15:43   2011-05-18, 16:59   #32
axn

Jun 2003

37·127 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).
In PARI, you'd do znorder(Mod(2,q)) to get the "order of 2 modulo q".   2011-05-18, 17:25   #33
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts Quote:
 Originally Posted by axn In PARI, you'd do znorder(Mod(2,q)) to get the "order of 2 modulo q". Google "group theory order"
Wikipedia would lead me to believe this means that q^2 mod q = p using that search.   Thread Tools Show Printable Version Email this Page 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 10:04.

Wed Sep 30 10:04:18 UTC 2020 up 20 days, 7:15, 0 users, load averages: 1.13, 1.33, 1.32