[ *August 15, 2004* ]

Find larger and larger palindromic primes

dividing numbers of the form k.b^{n} ± 1 (k > 1)

Finding larger and larger examples will be the challenge.

Here is your chance to add your name to the table !

[k,b,n,±1] | Palindromic prime | When | Who |

[k,b,n,±1] | ? | ? | ? |

[463,2,4537,–1] | 1003001 | August 16, 2004 | Patrick De Geest |

Good luck!

[ *September 24, 2004* ]

Jean Claude Rosa (email) adds some theory to the topic !

Finding solutions with k = 1 is not at all difficult

because of Fermat's Little Theorem :

"If n is prime and b < n then b^{n–1}–1 is divisible by n."

So for any palindromic prime pp, with b inferior to pp,

we have b^{(pp-1)}-1 divisible by pp.

E.g. if pp = 96769 then 2^{96768}–1 is divisible by 96769

but also b^{96768}–1 is divisible by 96769 for any

value of b that is smaller than 96769.

That is the reason why the cases with k different from 1

are the most interesting for this puzzle.

ps. PDG found also that 3^{576}+1 is divisible by 96769 :

This can be explained as follows : 96768 = 168 * 576 hence

3^{(576*168)}–1 is divisible by 96769. This means

either 3^{576} = 1 mod 96769 or 3^{576} = –1 mod 96769.

Your solution corresponds with the second possibility

described above. In fact if we are given a palprime pp,

we can find for certain (with greater or lesser difficulty)

a number 'b' and a number 'n' such that b^n + 1 is divisible

by pp, we only need to divide 'pp–1' by 2, by 4, etc.