[seqfan] phi(n) = b^c for some n, c > 1

Charles Greathouse charles.greathouse at case.edu
Tue Jul 16 04:43:42 CEST 2013


In a comment at A065528, Joseph L. Pe asks what b values appear with c > 1
as phi(n) = b^c. A numerical search found all even numbers under 50,000,
leading to the natural (?) conjecture that all even b > 0 appear.

Is this reasonable? Can it be proved, perhaps under some standard
assumption like Dickson's conjecture?

A plausibility argument: If b/2 is composite there are many choices of
primes to use; practically, this is the "easy case". If b/2 is prime then
the only primes which could divide a number n such that phi(n) = b^c are
* 2
* Fermat primes
* primes of the form 2^x * (b/2)^y + 1 with x <= y
There are something like log^2 t numbers of the third form up to t, so the
expected number of them which are prime is log t. Vigorous hand-waving,
along with the mantra "Borel-Cantelli", gives at least one (in fact
infinitely many) primes of the third kind; then primes of the other two can
round out the number so phi of the product is a power of b.

In the process of investigation I have submitted three related
sequences, A227533, A227534, and A227535. Feel free to add comments,
formulas, etc.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University


More information about the SeqFan mailing list