2
$\begingroup$

In base $b=10$, all prime numbers (except $2$ and $5$) end with one among the four symbols $1,3,7,9$. Therefore, between $10\cdot k$ and $10\cdot (k+1)$, there can be found $0,1,2,3$ or $4$ prime numbers.

In which base $b_N$ do all prime numbers end with one among $N$ symbols? And how many primes can be found between $b_N\cdot k$ and $b_N\cdot (k+1)$?

I apologize in case this is an obvious question. However, thanks for your help!

$\endgroup$
  • $\begingroup$ By Dirichlet's theorem, any digit coprime to the base will end infinitely many primes. $\endgroup$ – Benedict Randall Shaw Oct 18 '18 at 7:10
  • $\begingroup$ @BenedictRandallShaw Thanks for your comment. But I did not understand how it is related to the question. Please, can you expand a bit your observation? Thanks again! $\endgroup$ – user559615 Oct 18 '18 at 7:45
  • 1
    $\begingroup$ Euler's totient function, EulerPhi[n] in Mathematica, eulerphi(n) in Maple if I recall correctly. See Sloane's oeis.org/A000010 $\endgroup$ – Robert Soupe Oct 19 '18 at 4:17
  • 1
    $\begingroup$ Note that mathematicians have not been able to prove that the number of primes in one block of length $b_N$ can actually be as high as $N$ for some values of $k$. This is essentially equivalent to the prime $k$-tuples conjecture which is unsolved (but generally believed to be true). In recent years we were able to show that at least the count of primes can be much higher than $1$ (but very far from $N$), and that was a major breakthrough! $\endgroup$ – Erick Wong Oct 19 '18 at 19:23
  • 1
    $\begingroup$ @AndreaPrunotto We are 100% sure these are the only values generating $10$. It is easy to obtain a finite complete list of possible prime factors of any $n$ satisfying $\phi(n)=k$, and the exponents are even easier to bound. See math.stackexchange.com/q/586336/30402 for concrete examples. $\endgroup$ – Erick Wong Oct 20 '18 at 3:16
2
$\begingroup$

This behaviour is because $10$ itself is not prime.

Consider some other non-prime bases.

$16$ - Hexadecimal - With extra symbols $A, B, C, D, E, F$. Numbers ending in $0, 2, 4, 6, 8, A, C, E$ will never be prime since they will be even.

$12$ - With extra symbols $A, B$. Numbers ending in $0, 2, 3, 4, 6, 8, 9, A$ will never be prime since they will be multiples of $2$ or $3$ or both.

Consider prime bases.

$2$

Apart from $2$ itself, which will appear as $10$ in base $2$, numbers ending in $0$ won't be prime. Primes can be found ending in any other digit. Of course, any other digit is just $1$ so that is not very interesting.

$7$

Primes can be found ending in any digit other than $0$.

Similarly, to base $2$, $7$ will appear as $10$. Any other number ending in $0$ will not be prime.

Other bases

In general, a number written in its own base will appear as $10$ hence if the base is prime then this will be prime. Avoid thinking of $10$ as "ten" when working in alternative bases.

What Benedict is saying is that my example of $7$ is typical of prime bases. If the base is prime then you can find primes ending in any digit other than $0$. Actually, he is saying a bit more. You will be able to find infinitely many primes ending in a digit other than $0$. More still, even if the base is not prime, if the digit is coprime to the base then you can find infinitely many primes ending in it. So, infinitely many primes end in $1$ in base 2 (this just says that there are infinitely many odd primes). Also infinitely many primes end in $7$ in base $10$.

This may help: Dirichlet's theorem on arithmetic progressions

$\endgroup$
  • $\begingroup$ Thanks for your answer. I think I got it now. Some obervations: Given then a non-prime base, is there a general rule to predict how many ending digits are characteristically related to prime numbers in that base? Moreover, is it maybe possible to find 2, 3, or more ending digits (i.e. not only one symbol, but combinations of symbols), which characterize the primes in other bases? $\endgroup$ – user559615 Oct 18 '18 at 8:41
  • 1
    $\begingroup$ Remember that what is important is whether the ending digit is coprime to the base. If it is then infinitely many primes will end in it. If it isn't then none will. So, you are asking how to find how many numbers less than $n$ are coprime to $n$. This is certainly studied and maybe deserves its own question. $\endgroup$ – badjohn Oct 18 '18 at 8:49
  • $\begingroup$ Multiple ending digits are easy to handle. Consider 2 ending digits in base 10. This is just like using base 100. Group the digits into pairs and regard them as a symbol in base 100. So, which 2 digit numbers are coprime to 100? $\endgroup$ – badjohn Oct 18 '18 at 8:50
  • $\begingroup$ @FabioSomenzi Thanks, a silly mistake, I'll correct it. $\endgroup$ – badjohn Oct 19 '18 at 19:08
  • 1
    $\begingroup$ For prime bases such as $2$ and $7$, the prime itself will be represented as $10$ and thus end in $0$. No larger primes would end in $0$ as that would make them multiples of the prime base. $\endgroup$ – Keith Backman Oct 20 '18 at 1:27
0
$\begingroup$

Since all primes other than $2$ and $3$ are of the form $6k\pm 1$, in base $6$, all such primes end in either $1$ or $5$. Thus at least one prime will be found in base $6$ with any terminal digit other than $0$ or $4$, although the terminal digits $2$ and $3$ occur only once.

$\endgroup$

Your Answer

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