mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2011-03-31, 15:22   #23
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-03-31, 16:01   #24
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-03-31, 16:05   #25
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·52·79 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2011-03-31, 16:10   #26
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-03-31, 17:24   #27
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-03-31, 18:26   #28
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-03-31, 18:40   #29
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×52×79 Posts
Default

Right, of course. I can't see or think straight today...
CRGreathouse is offline   Reply With Quote
Old 2011-03-31, 20:42   #30
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-05-18, 15:42   #31
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

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
science_man_88 is offline   Reply With Quote
Old 2011-05-18, 16:59   #32
axn
 
axn's Avatar
 
Jun 2003

37·127 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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".

Google "group theory order"
axn is online now   Reply With Quote
Old 2011-05-18, 17:25   #33
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by axn View Post
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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 5: rationals & intro to modular arithmetic Nick Number Theory Discussion Group 1 2016-10-21 22:21
modular arithmetic problem JuanTutors Math 4 2009-03-11 16:06
need C/C++ modular arithmetic code for Windows ixfd64 Programming 15 2008-07-30 03:52
Modular Arithmetic Numbers Math 27 2005-11-30 15:41
Jim Howell's modular arithmetic program? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.