2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ When writing down things like this, I find it useful to give several examples of how to do the dividing into concatenated strings, in basis ten and then also in some other basis. $\endgroup$ – Timbuc May 9 '15 at 20:14
  • $\begingroup$ Thank you for the helpful suggestion Timbuc. For now I just added an example in base 10, but it is the same logic in any base. Anyway when I have the time I might include other examples. $\endgroup$ – Fernando Pimentel May 9 '15 at 21:02
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Even without having yet explored the interesting references provided, or considered the possibility of other answers, from the first paragraphs I have accepted this answer for the most valuable link to consider the problem in the polynomials framework, which might be quite helpful for my future PhD work behond this question. Besides the fact that it works, the answer provided me with the neccessary general setting without leaving the specificity of the digit expansion behind. So thank you very much. $\endgroup$ – Fernando Pimentel May 9 '15 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.