[ August 15, 2004 ]
Find larger and larger palindromic primes
dividing numbers of the form k.bn ± 1 (k > 1)
Finding larger and larger examples will be the challenge.
Here is your chance to add your name to the table !
|[463,2,4537,1]||1003001||August 16, 2004||Patrick De Geest|
[ 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 bn11 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 2967681 is divisible by 96769
but also b967681 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 3576+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 3576 = 1 mod 96769 or 3576 = 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 'pp1' by 2, by 4, etc.