Is This a Prime?

Someone once asked me if 785645465756452 is a prime.  Presumably the
base of the representation is not 10, since otherwise the number is
obviously a multiple of 2.  On the other hand, we note that for ANY 
base, the number is not divisible by 3.  Similarly, it cannot be 
divisible by 17, 23, 41, 47, 53, etc...  regardless of what base is 
assumed.

It isn't too hard to show that 23 is the only (positive) base less 
than 100 for which the number is actually prime.  The next bases for
which the number is prime are 165, 189, 193, 345, 399, 455, etc.

Incidentally, converted from base 23 to base 10, the number is

                      85297610194238336897

Notice that each of the ten decimal digits 0,1,..,9 appears at least
once in this number.  In contrast, the original number has no 0, 1, 3,
or 9, whereas it contains five 5s in the pattern xx5xx5xx5x5xx5x.  The
overall digit frequency is

           digit   0  1  2  3  4  5  6  7  8  9
     occurrences   0  0  1  0  3  5  3  2  1  0

Can we infer anything from this about how the original digits were 
selected?

A more interesting question is:  Given an irreducible polynomial P(x) 
of degree > 0 with integer coefficients, does there necessarily exist 
an integer n such that P(n) is a prime?  Of course, Dirichlet's Theorem
states that there are infinitely many such n for any irreducible 
polynomial of degree 1.  According to Ribenboim, the answer to the
more general question is unknown.   For most (irreducible) polynomials
P(x) it's usually easy to find an integer n such that P(n) is prime,
but for certain polynomials it's surprisingly difficult.  For example,
the least positive n such that n^(12) + 488669 is prime is n = 616979.

It's also interesting to note that if exponential expressions are
allowed, we can have no primes at all in certain sequences. For 
example, the number 

               2935363331541925531 * 2^n  +  1 

is never a prime number (as can be proved by factoring the multipler 
minus 1). See Richard Guy's Unsolved Problems in Number Theory for 
more examples.

Return to MathPages Main Menu