1
$\begingroup$

In base $10$, all prime numbers (a part $2$ and $5$) end with $1,3,7$ or $9$, i.e. with four different symbols.

Is there a base in which all prime numbers end with $5$ different symbols (or also with $5$ distinct groups of symbols)? If yes, which base?

Thanks for your help! I apologize for such a trivial question!

NOTE: This question is related to this one.

$\endgroup$
  • 2
    $\begingroup$ Is $5=\phi(n)$ for some $n$? $\endgroup$ – Lord Shark the Unknown Oct 19 '18 at 18:47
  • 1
    $\begingroup$ Comments in the linked question advised you to study Euler's totient function $\phi(n).\,$ Did you do so before posting this question? If so, where are you stuck? If not, then you should do so. $\endgroup$ – Bill Dubuque Oct 19 '18 at 18:48
  • $\begingroup$ Yes, but I did not understand much. I understood, as @LordSharktheUnknown said, that this is related to the totient function. But I don't know if I can evaluate all its values, since there is not a formula for the primes. Or what am I missing? $\endgroup$ – user559615 Oct 19 '18 at 18:52
  • 1
    $\begingroup$ There is no $n$ such that $\phi(n)=5$, as $\phi(n)$ is even for $n>2$. $\endgroup$ – Inactive - Objecting Extremism Oct 19 '18 at 19:09
  • $\begingroup$ @Servaes But sure! Many, many thanks! $\endgroup$ – user559615 Oct 19 '18 at 19:14
0
$\begingroup$

In base $b$, all prime numbers that do not divide $b$ end in a number between $0$ and $b$ coprime to $b$. Conversely, for every number between $0$ and $b$ coprime to $b$, there is a prime number ending in $b$. This follows from the prime number theorem for arithmetic progressions, for example. So the question becomes; for which numbers $b$ are there precisely $5$ numbers between $0$ and $b$ that are coprime to $b$. This number is denoted by $\phi(b)$, where $b$ is Euler's totient function. It is a simple result that $\phi(b)$ is even for all $b>2$, for example from the identity $$\phi\left(\prod_{i=1}^np_i^{k_i}\right)=\prod_{i=1}^np_i^{k_i-1}(p-1),$$ where the $p_i$ are distinct primes and the $k_i$ are positive integers.


In fact the only bases $b$ with $\phi(b)<5$ are $b=2,3,4,5,6,8,10,12$. Only in bases $5$ and $8$ do we get precisely $5$ different symbols in which primes can end, where we also count the divisors of the base.

$\endgroup$
  • $\begingroup$ Thanks again! Also to the other users! $\endgroup$ – user559615 Oct 19 '18 at 19:16
  • 1
    $\begingroup$ @AndreaPrunotto There is a simpler proof by reflection (negation) symmetry - see my answer. $\endgroup$ – Bill Dubuque Oct 19 '18 at 19:59
1
$\begingroup$

Hint $ $ The number of residues coprime to $n> 2$ is even: $ $ negation reflection $\,x\mapsto -x\pmod {\!n}\,$ partitions them into pairs (since it has no fixed points: $\,-a\equiv a\,\Rightarrow\, n\mid 2a,\,$ contra $(n,a)=1)$.

Remark $\ $ Such use of reflections (or involutions) to pair-up terms frequently proves handy, e.g. see prior posts here on Wilson's theorem (in groups), esp. this one to start.

$\endgroup$
  • $\begingroup$ Thanks for the clever answer! I have to study more!!!! $\endgroup$ – user559615 Oct 19 '18 at 20:52
  • $\begingroup$ Just a little, further question. Is there a way to be sure that, for instance, $\phi(n)=10$ only for $n=10$ and $n=11$? $\endgroup$ – user559615 Oct 19 '18 at 22:24
  • $\begingroup$ @AndreaPrunotto $\phi(10) = 4$ as you mention in your question. You can use the formula for $\phi$ for things like that (see many prior questions). $\endgroup$ – Bill Dubuque Oct 19 '18 at 22:51

Your Answer

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