[ August 15, 2004 ]
Find larger and larger palindromic primes
dividing numbers of the form k.bⁿ ± 1 (k > 1)

Finding larger and larger examples will be the challenge.
Here is your chance to add your name to the table !

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⁹⁶⁷⁶⁸–1 is divisible by 96769
but also b⁹⁶⁷⁶⁸–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⁵⁷⁶+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⁵⁷⁶ = 1 mod 96769 or 3⁵⁷⁶ = –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.