Thread: On prime chains
View Single Post
Old 2009-08-20, 10:54   #4
Kevin's Avatar
Aug 2002
Ann Arbor, MI

433 Posts

Originally Posted by Dougy View Post
There'd also be some others. For example if (a,b)=(3,1) and p(k) is odd, then p(k+1)=3*p(k)+1 is even. Lehmer didn't explain this very well... hmm...
I suppose something similar happens anytime there exists an N for which a=1 mod N and b is coprime to N. Working modulo N, p(k)=p(0)+kb mod N, so you'll always get something divisible by N when k=p(0)*b^-1. I feel like there should be a few more ways you can "trivially" guarantee a factor of N in a bounded number of steps if a,b, and N satisfy certain relations, but I'm not prepared to take that on or look up the reference since it's close to 6am local time.
Kevin is offline   Reply With Quote