 My Math Forum Finding modular relations among numbers of the form 2^k + n
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 January 14th, 2008, 01:09 PM #1 Global Moderator   Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Finding modular relations among numbers of the form 2^k + n I was working on a problem with numbers of the form 2^k+n for k (potentially) large and n fixed. I pre-sieve candidate primes in the range by finding a value f such that whenever k = f (mod p-1) it holds that p | 2^k+n, and test a large range of k values. 1. The search for such an f is computationally expensive, since I search in an essentially brute-force manner. Is there a number-theoretic way of getting this directly? I feel like there should be. 2. Sometimes 'more is true': whenever k = f (mod m) it holds that p | 2^k+n, for some m | p-1. Since I test the f values sequentially, this is not the case if 2f > p-1. When 2f < p-1, is there a good way to find values of m that work? The second part, refining the modular classes, is probably more important than the first, since smaller modular classes are much more meaningful than large. January 15th, 2008, 05:56 AM #2 Global Moderator   Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Actually, the problem is perhaps more about abstract algebra than number theory -- the order of an element in the [color=gray](--group Z/p--)[/color]. I don't think the result I want is particularly complicated... it's just a thing I've forgotten. Edit: the above [color=gray]portion[/color] should read "commutative monoid on {0, 1, 2, ..., p-1} induced by multiplication mod p". January 15th, 2008, 08:28 PM #3 Senior Member   Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3 Not sure if this actually helps, but the order of any element of Z/p is p or a factor of p... We'll call the element in question a. |a|=p/gcd(p,a); So with the example Z/30 |a|=1, a={0} |a|=2, a={15} |a|=3, a={10,20} |a|=4, a={} (4 does not divide 30) |a|=5. a={6,12,18,24} ... Does that help? January 16th, 2008, 06:22 AM #4 Global Moderator   Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Sorry, I didn't mean what I wrote. I was actually talking about the commutative monoid on {0, 1, 2, ..., p-1} induced by multiplication mod p. The order of a given element divides phi(p). Examples mod 29: |a| = 28 for a in {2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27} |a| = 14 for a in {4, 5, 6, 9, 13, 22} |a| = 7 for a in {7, 16, 20, 23, 24, 25} |a| = 4 for a in {12, 17} |a| = 2 for a = 28 |a| = 1 for a = 1 Tags finding, form, modular, numbers, relations Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post Das Bot Number Theory 6 March 5th, 2013 12:33 PM Fernando Number Theory 2 May 23rd, 2012 12:10 AM Bogauss Number Theory 15 January 12th, 2011 10:05 AM CRGreathouse Applied Math 2 April 22nd, 2010 05:30 AM momo Number Theory 8 December 27th, 2009 02:53 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      