My Math Forum Finding modular relations among numbers of the form 2^k + n

 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 Display Modes Linear 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