My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
January 14th, 2008, 01:09 PM   #1
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
 
January 15th, 2008, 05:56 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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".
CRGreathouse is offline  
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?
cknapp is offline  
January 16th, 2008, 06:22 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 (p-1!) 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





Copyright © 2019 My Math Forum. All rights reserved.