
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
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 presieve candidate primes in the range by finding a value f such that whenever k = f (mod p1) 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 bruteforce manner. Is there a numbertheoretic 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  p1. Since I test the f values sequentially, this is not the case if 2f > p1. When 2f < p1, 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, ..., p1} 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, ..., p1} 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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Finding smallest solution to modular equations  Das Bot  Number Theory  6  March 5th, 2013 12:33 PM 
Form of the numbers  Fernando  Number Theory  2  May 23rd, 2012 12:10 AM 
Prime numbers of the form p^p mod (p1!)  Bogauss  Number Theory  15  January 12th, 2011 10:05 AM 
Relations, attributes, and counting to really big numbers  CRGreathouse  Applied Math  2  April 22nd, 2010 05:30 AM 
Prime numbers of the form p= k!/(a+b)+a  momo  Number Theory  8  December 27th, 2009 02:53 PM 