Accidentally found ?th conjecture for R38, need explanation

[Puzzle-Peter]

Hi all,

as a little diversion I decided to try to find a "birthday twin" for a friend. So I used the date of birth and the age at the next celebration to search for 19780108*38^n +/-1. To my amazement, no candidate of the -1 side survived.

A quick test with pfgw tells me that every candidate is divided by either 3, 5, 7 or 17. in a recurring pattern. Starting with n=1 the divisors are (7, 3, 5, 3, 17, 3, 5, 3, 17, 3, 5, 3) then the cycle restarts.

I have an engineer's maths skills, but that involves just about zero number theory. Is there an easy way to explain how I can prove that 19780108*38^n-1 will never be prime?

Thanks.

[axn]

Originally Posted by Puzzle-Peter

Hi all,

as a little diversion I decided to try to find a "birthday twin" for a friend. So I used the date of birth and the age at the next celebration to search for 19780108*38^n +/-1. To my amazement, no candidate of the -1 side survived.

A quick test with pfgw tells me that every candidate is divided by either 3, 5, 7 or 17. in a recurring pattern. Starting with n=1 the divisors are (7, 3, 5, 3, 17, 3, 5, 3, 17, 3, 5, 3) then the cycle restarts.

I have an engineer's maths skills, but that involves just about zero number theory. Is there an easy way to explain how I can prove that 19780108*38^n-1 will never be prime?

Thanks.

The covering set is {3,5,17}. 3 will divide every other number starting at n=0 (so all even indexed numbers). 5 will divide every 4th index starting at n=3, and 17 will divide every 4th index at starting at n=1. So this pattern {3,17,3,5} will repeat every 4 index, thus covering all indices.

[LaurV]

Originally Posted by Puzzle-Peter

Is there an easy way to explain how I can prove that 19780108*38^n-1 will never be prime?

You just did that. As k=19780108 is 1 (mod 3) and 38^n is 1 (mod 3) for all n=even powers, than every second k*b^n-1 is 0 (mod 3).
Repeat for 5, 17.
Also, 7 divides every 6th.

[edit: grrr... axn!]

[Puzzle-Peter]

Originally Posted by axn

The covering set is {3,5,17}. 3 will divide every other number starting at n=0 (so all even indexed numbers). 5 will divide every 4th index starting at n=3, and 17 will divide every 4th index at starting at n=1. So this pattern {3,17,3,5} will repeat every 4 index, thus covering all indices.

I'm afraid we need to go a bit more basic here. When I look at the sequence, how do I tell that e.g. 17 will divide every 4th index starting at n=1 ?

[LaurV]

Originally Posted by Puzzle-Peter

I'm afraid we need to go a bit more basic here. When I look at the sequence, how do I tell that e.g. 17 will divide every 4th index starting at n=1 ?

38=4 (mod 17). So, when multiplying with itself (mod 17) you get 17^2=4*4=16=-1 (mod 17), 17^3=-1*4=-4, and so on. So, the string of powers of 38 (mod 17), starting with zeroth power, is: 1, 4, 16, 13, 1, 4, 16, 13, etc (or, 1, 4, -1, -4, etc). Your k is 13 (mod 17), or -4 mod 17, if you prefer. So the string of k*b^n will be 13, 1, 4, 16, 13, 1, 4, 16, etc. And when you subtract 1, you get a zero every 4 positions, i.e. k*b^(n=4x+1)-1 is divisible by 17.

[Puzzle-Peter]

Originally Posted by LaurV

37=4 (mod 17). So, when multiplying with itself (mod 17) you get 17^2=4*4=16=-1 (mod 17), 17^3=-1*4=-4, and so on. So, the string of powers of 38 (mod 17), starting with zeroth power, is: 1, 4, 16, 13, 1, 4, 16, 13, etc (or, 1, 4, -1, -4, etc). Your k is 13 (mod 17), or -4 mod 17, if you prefer. So the string of k*b^n will be 13, 1, 4, 16, 13, 1, 4, 16, etc. And when you subtract 1, you get a zero every 4 positions, i.e. k*b^(n=4x+1)-1 is divisible by 17.

Thanks, that's what I needed.

So to find a covering set, you just have to try and find such patterns or is there a faster way to get to {3, 5, 17} ? These are pretty low numbers, but once they get bigger, trial and error will be pretty annoying I guess.

I have no idea how one would start looking for the smallest conjectured k for a new base.

[LaurV]

Well, technically this fits when you know the set already. Another way to "prove" that story with 17 it would be just to show that k*b^(4n+1)=1 (mod 17) for your k, b, and any n, which is a simple modular calculus. That is k*(b^4)^n*b, or -4*1^n*4, or -(-1), i.e. 1 (mod 17).

For the second part, to search for covering sets (and implicitly the smaller k), you factor k*b^n+/-1 for few small n (like, from 1 to 20, is enough) and for a particular k and b, and "look" to the factors, see how they repeat. Eventually, you sieve for higher n with those factors you already got, but there is a very low chance that you get a covering set of more than 10-20 primes, so the "sieving" part is not necessary most of the time. But that is how covering sets of (a, b, c, d) were found, where a,b,c are 1-3 digits primes and d is a very big prime.

Then do it for as many k you like, till you find one with the reasonable covering set. (or, say, with "any covering set").

[Puzzle-Peter]

Great, thank you!