reference request - The following is a necessary condition for a number to be prime, from its digit expansion. Has it been referred somewhere?

Concerning a numbers’ digits we know some necessary conditions on them for the number to be prime, besides the last digit having to be odd (except for prime 2). For example in decimal representation the last digit can not be 5, and the sum of the digits of the number can not be divisible by 3.
But has the following result been referred somewhere?

1. If we take the digit expansion of a natural number $n$ in positional notation with its $m$ digits divided into two continuous concatenated strings $a$ and $b$ such that:

   
   
   

   $$n=a2^k+b\text{ with }$$

   
   
   

   $$b=b_0r^0+\cdots+b_{k-1}r^{k-1}$$

   
   
   
   

   $$a=a_0r^0+\cdots+a_{m-k-1}r^{m-k-1}$$

   
   
   

   $r=$ radius (of the base where the number is represented)

   
   
   

   $m=$ number of digits of $n$ ($m>k$)




2. Then we might state the following necessary condition over the number’s digit expansion so that it is prime:

   
   
   

   For any $b>1$, there cannot be any $k$ such that $a \text{ mod }b = 0$

   
   
   

   Proof: If there were, we could write $n$ as a product:

   
   
   
   

   $$n=(\dfrac{a}{b}r^k+1)b$$

Example:

Take the number 637 in base 10. You have to check all possible two-string concatenation combinations with a>=b.

In this case its simple, it works dividing the number digits the following way: a='63' and b='7'.

Since a/b = 63/7=9 you can write 637=((63/7)*10 + 1)*7

So 637 cannot be prime.

I realized this property while working in a “number system” different from our own, where the arithmetic is different. Then Gustavo Granja kindly arrived at this formulation, which is the equivalent in our “usual” number system.

It seems too easy not to be known. In MathOverflow I got the following helpful comment from Gerhard Paseman: "This is a specific version of something more general: If $n=ac +b$ with $a,b,c$ positive, and $b > 1$, then $b|a$ implies $n$ is not prime".

However, in spite of that general case, I find it interesting (and eventually helpful for factorization purposes) that sometimes we can realize this directly from the digits of a number, without divisibility tests involving any information other than the one we have right before our eyes.

So I wonder if this has been previously mentioned somewhere.

Answer

Your observation is a special case of content-based factors of polynomials.

Suppose that $\,f(x)\,$ is a nonconstant polynomial whose coefficients are all nonnegative integers. $\ \ $ If $\,f\,$ has nontrivial content, i.e. if the gcd $\,d\,$ of all of the coefficients of $\,f\,$ is $>1,\,$ then it follows that $\,d\mid f(n)\,$ properly for all $\,n>1,\,$ so $\,f(n)\,$ is composite for all $\,n>1$.

This applies to OP because radix notation is polynomial function of the radix (of above type).

Remark $\ $ There are many interesting relationships between the factorization properties of polynomials and their values. For example, in $1918$ Stackel published the following

Theorem If $\rm\, f(x)\,$ is a composite integer coefficient polynomial then $\rm\, f(n)\, $ is composite for all $\rm\,|n| > B,\, $ for some bound $\rm\,B.\,$ In fact $\rm\, f(n)\, $ has at most $\rm\, 2d\, $ prime values, where $\rm\, d = {\rm deg}(f)$.

The simple proof can be found online in Mott & Rose [3], p. 8.

Contrapositively, $\rm\, f(x)\, $ is prime (irreducible) if it assumes a prime value
for large enough $\rm\, |x|\, $.
As an example, Polya-Szego popularized A. Cohn's irreduciblity test, which
states that $\rm\, f(x) \in \mathbb Z[x]\,$ is prime if $\rm\, f(b)\, $
yields a prime in radix $\rm\,b\,$ representation (so $\rm\,0 \le f_i < b).$

For example $\rm\,f(x) = x^4 + 6\, x^2 + 1 \pmod p\,$ factors for all primes $\rm\,p,\,$
yet $\rm\,f(x)\,$ is prime since $\rm\,f(8) = 10601\rm$ octal $= 4481$ is prime.
Cohn's test fails if, in radix $\rm\,b,\,$ negative digits are allowed, e.g.
$\rm\,f(x)\, =\, x^3 - 9 x^2 + x-9\, =\, (x-9)\,(x^2 + 1)\,$ but $\rm\,f(10) = 101\,$ is prime.

Conversely Bouniakowski conjectured $(1857)$
that prime $\rm\, f(x)\, $ assume infinitely many prime values (excluding
cases where all the values of $\rm\,f\,$ have fixed common divisors, e.g. $\rm\, 2\: |\: x(x+1)+2\, ).$ However, except for linear polynomials (Dirichlet's theorem), this conjecture has never been proved for any polynomial of degree $> 1.$

Note that a result yielding the existence of one prime value extends to existence of infinitely many prime values, for any class of polynomials closed under shifts, viz. if $\rm\:f(n_1)\:$ is prime, then $\rm\:g(x) = f(x+ n_1\!+1)\:$ is prime for some $\rm\:x = n_2\in\Bbb N,\:$ etc.

For further detailed discussion of Bouniakowski's conjecture and related results, including heuristic and probabilistic arguments, see Chapter 6 of Ribenboim's The New Book of Prime Number Records.

[1] Bill Dubuque, sci.math 2002-11-12, On prime producing polynomials.

[2] Murty, Ram. Prime numbers and irreducible polynomials.
Amer. Math. Monthly, Vol. 109 (2002), no. 5, 452-458.

[3] Mott, Joe L.; Rose, Kermit. Prime producing cubic polynomials.
Ideal theoretic methods in commutative algebra, 281-317.
Lecture Notes in Pure and Appl. Math., 220, Dekker, New York, 2001.