Problems & Puzzles: Puzzles

Puzzle 510. nrp(2^m) = m + 2

Fred Schneider poses the following puzzle:

Note the following:

phi(x) = 2 = 2^1 where x=3,4, or 6

phi(x) = 4 = 2^2 where x = 5, 8, 10, 12

phi(x) = 8 = 2^3 where x = 15, 16, 20, 24, 30

Let nrp(n) be defined as the exact number of distinct positive
integers x such that phi(x) =n

So, nrp(2) =3, nrp(4) = 4, nrp(8) = 5

Q1. Can you show that nrp(2^m) = m + 2 for all integers m> 0? If not, what is the first exception?

Q2. Can you explain why this pattern occurs?

 

Contributions came from Farideh Firoozbakht, Antoine Verroken, Dan Dima, Luca Poletti & J. K. Andersen

***

Farideh wrote:

" for each number n, n > = 0 there exists only one odd
number m such that phi(m) = 2^n " (*)

phi(x) = 2^n (1)

phi(x) = 2^(n+1) (2)

If (*) is true then by induction we show that number of solutions for (1) is n+2.

In fact by using the set of all n+2 solutions for the equation (1) and the only odd solution
for the equation (2) we obtain all (n+1)+2 solutions of (2).

Proof :

Suppose that (*) is true and let the only odd solution of (1) be f(n) also set of n+2
solutions for (1) be A(n) = {f(n), 2 f(n), m(1), m(2), ..., m(n)} .

It's obvious that each term of the set B = {f(n+1), 2 f(n+1), 4 f(n), 2 m(1), 2 m(2), ...,
2 m(n)} is a solution for (2), namely B is a subset of A(n+1).
Now if c is an even solution for (2) then obviously c>2, so
phi(1/2*c) = 1/2*phi(c) = 1/2*2^(n+1) = 2^n, hence according to the definition of
A(n), 1/2*c is in A(n), so c is in B. Also if c is an odd solution for (2) according t0 (*)
c = f(n+1), so in both cases c is in B. Namely A(n+1) is a subset of B.
Hence A(n+1) = B and the proof is complete by considering that that A(0) = {1, 2}
has 0+2 members.

As I wrote, I don't know (*) is true or not. So we must work on (*).
 

***

Antoine wrote:

According to Prof. R.D. Carmichael in Bull. Amer. Math. Soc. 1907 , 13 , 5 , p 241-243 :

Q1 : up to m = 31 the number of solutions is ( m + 2 ) ; from m = 32 to m = 255 the num-
ber of solutions remains constant and is 33.

Q2 : cfr. annex Euler phi-function Carmichael.

***

Dan wrote:

The answer to this puzzle is related to Fermat numbers and their primality.

Immediately it can be seen that any solution x must be of the form:
x = 2^k * o, o - odd squarefree integer


The equation phi(x) = 2^m has at most one odd solution.

More precisely it has exactly one odd solution if and only if:
- each of the 2^(2^j(i)) + 1 is a Fermat prime number
where 0 <= j(1) < ... < j(k) are distinct integers from
the binary representation of m as: m = sum(1<=i<=k,2^j(i))

If at least one of the Fermat numbers 2^(2^j(i)) + 1 is a composite integer then
there is no odd solution for the equation phi(x) = 2^m.

x = p(1)*...*p(k), p(i)-odd primes, 1<=i<=k
phi(x) = 2^m
phi(x) = (p(1)-1)*...*(p(k)-1)
the unique binary representation of m as: m = sum(1<=i<=k,2^j(i))
p(i)-1 cannot be of the form
2^l(i)+1 where l(i) not a power of 2 because p(i) would not be prime anymore
Hence p(i)-1 = 2^(2^j(i)) + 1 and then it follows then uniqueness of
any possible odd solution.
Indeed from m = sum(1<=i<=k,2^j(i)) and each of the 2^(2^j(i)) + 1 as
a Fermat prime number
it follows that exists exactly one odd solution otherwise there is no solution.

If exists the odd solution of:

phi(o) = 2^m
m = sum(1<=i<=k,2^j(i))
is:
o = prod(1<=i<=k,2^(2^j(i)) + 1)

If there is an odd solution o to the equation phi(o) = 2^m then 2*o is
also a solution as phi(2*o) = 2^m.


All the solutions of the equation phi(x) = 2^m can be characterized as
it follows:
- one possible odd solution o and the corresponding 2*o
- solutions of the form 2^k * o' where o'-odd prime, k>1 - at least
multiple by 4 or larger powers of 2


Relation between solutions of phi(x) = 2^m and phi(x) = 2^(m+1)

If phi(x) = 2^m has the possible solution o and the corresponding 2*o then
4*o is a solution to phi(x) = 2^(m+1).
There is a one to one correspondence between the solution at least
multiple by 4 of phi(x) = 2^m
and the solution at least multiple by 8 of phi(x) = 2^(m+1)
x - divisible by 4
phi(x) = 2^m <=> phi(2*x) = 2^(m+1)


Taking into account the known facts about the Fermat numbers
http://en.wikipedia.org/wiki/Fermat_number
http://mathworld.wolfram.com/FermatNumber.html
we get:

2^(2^n)+1 is prime for 0<=n<=4 and composite for 5<=n<=32
and many other larger Fermat numbers proved as composite - see
http://www.prothsearch.net/fermat.html#Summary
No other larger Fermat prime numbers are known and there is
conjectured there are no other such numbers.


Hence we have a complete behaviour depending on primality of Fermat numbers:

Indeed nrp(2^m) = m + 2 for all integers 0<m<32
nrp(2)=3,
nrp(2^2)=4,
nrp(2^3)=5,
...
nrp(2^31)=33
Each m, 0<m<32, m = sum(1<=i<=k,2^j(i)) and each 2^(2^i) + 1 is prime, 0<=i<=4
For next m as m=2^5 the Fermat number 2^(2^5) + 1 is composite so
nrp(2^32)=32
and considering that 2^(2^n)+1 is composite for all 5<=n<=32
nrp(2^m)=32 for all m, 32 <= m <= 2^33-1


Q1. 32 is the first exception as nrp(2^32)=32


Q2.
More precisely:
m - each of the 2^(2^j(i)) + 1 is a Fermat prime number
(m+1) - each of the 2^(2^j(i)) + 1 is a Fermat prime number
then:
nrp(2^(m+1)) = nrp(2^m)+1 (true for 0 < m < 31)

m - each of the 2^(2^j(i)) + 1 is a Fermat prime number
(m+1) - one of the 2^(2^j(i)) + 1 is a Fermat composite number
then:
nrp(2^(m+1)) = nrp(2^m)-1 (true for m = 31)

m - one of the 2^(2^j(i)) + 1 is a Fermat composite number
(m+1) - one of the 2^(2^j(i)) + 1 is a Fermat composite number
then:
nrp(2^(m+1)) = nrp(2^m) (true for 31 < m < 2^33 and other larger m)

m - one of the 2^(2^j(i)) + 1 is a Fermat composite number
(m+1) - each of the 2^(2^j(i)) + 1 is a Fermat prime number
then:
nrp(2^(m+1)) = nrp(2^m)+2 (not found yet)


If the conjecture that no other larger Fermat prime numbers exists then
nrp(2^m)=32 for all integers m>=32

If a next larger Fermat prime exists as F_f = 2^(2^f) + 1
nrp(2^m)=32 for all m, 32 <= m < 2^f
nrp(2^(2^f))=34
and all 0<k<32, nrp(2^(2^f+k))=34+k until nrp(2^(2^f+31))=65
nrp(2^(2^f+32))=64
and again nrp(2^(2^f+m))=64 for all m, 32 <= m < 2^33, etc

All these explain the pattern that occurs for nrp(2^m).

***

Luca wrote:

Q1. Can you show that nrp(2^m) = m + 2 for all integers m> 0? If not, what is the first exception?

False: It doesn't suite for all m.

a number x | phi(x)=2^m has the form: x=(2^a1+1)*...*(2^an+1)*2^(m-(a1+...+an)+1) or x=(2^a1+1)*...*(2^an+1) (if a1+...+an=m) where (2^ak+1) is prime. (A)

In fact phi(x)=2^a1*...*2^an*2^(m-(a1+...+an))=2^m

It can be demostrated that the only numbers of the form (2^ak+1) which are prime, are Fermat primes, up to now the greatest known is 65537.

So it can be build an exception (it may be the first but i'm not sure at all)

Set x=2*(2^2^0+1)*...*(2^2^4+1)=2*3*5*17*257*65537=4296277995, phi(x)=1*(2^2^0)*...*(2^2^4)=2147483648=2^31
all the numbers which are suitable:
x/2;
x*2^0/1;
x*2^1/3;
x*2^2/5; x*2^3/(3*5);
x*2^4/17; x*2^5/(3*17); x*2^6/(5*17); x*2^7/(3*5*17);
x*2^8/256; x*2^9/(3*257); x*2^10/(5*257); x*2^11/(3*5*257); x*2^12/(17*257); x*2^13/(3*17*257); x*2^14/(5*17*257); x*2^15/(3*5*17*257);
x*2^16/65537; x*2^17/(3*65537); x*2^18/(5*65537); x*2^19/(3*5*65537); x*2^20/(17*65537); x*2^21/(3*17*65537); x*2^22/(5*17*65537); x*2^23/(3*5*17*65537); x*2^24/(257*65537); x*2^25/(3*257*65537); x*2^26/(5*257*65537); x*2^27/(3*5*257*65537); x*2^28/(17*257*65537); x*2^29/(3*17*257*65537); x*2^30/(5*17*257*65537); x*2^31/(3*5*17*257*65537);

now we have obtained a <List> which show that nrp(2^31)=33;

If we try to build a list for nrp(2^32) we can have some y of the form y=2*x', that will be suitable only if 2|x' (2 divide x') and x' are some elements taken form <List>.
From (A) and <List> we can see that there are no other even number, and if an odd number exist it need to be either prime of the form 2^32+1 or squarefree, but 2^32+1 is not prime and a squarefree of the form (A) must be a product of Fermat primes, and x/2 is the greatest of that form.
So there no exist other number apart ones of the form y=2*x', with 2|x' and x' from <List>, so we obtain a total of 32 suitable numbers => npr(2^32)=32≠34

Q2. Can you explain why this pattern occurs?


<List> show why up to 2^31 that pattern occurs

***

Andersen wrote:

Q2. If x has prime factorization x = p1^a1*...*pk^ak then
phi(x) = x * (p1-1)/p1*...*(pk-1)/pk
= p1^(a1-1)*...*pk^(ak-1) * (p1-1)*...*(pk-1)

If phi(x) is a power of 2 then all factors in the latter expression
for phi(x) must be powers of 2 (possibly 2^0 = 1).
This means a1 to ak must all be 1, except that a1 can be any value if p1=2.
It also means p1-1, ..., pk-1 must all be powers of 2, so p1 to pk must
all be Fermat primes, except p1 which can also be 2.
Together the above means that phi(x) is a power of two if and only if
x is a power of 2 times any number of distinct Fermat primes.
By the way, that is also the condition for an x-sided regular polygon to
be constructible with compass and straightedge.

If x is of the required form with x = 2^b1*(2^b2+1)*...*(2^bk+1)
where p1=2 and b1 > 0, then phi(x) = 2^(b1-1)*2^b2*...*2^bk = 2^(b1-1 + b2+...+bk).
If x has no power of 2 (corresponding to b1=0), then it can be written
x = (2^b2+1)*...*(2^bk+1), and
phi(x) = 2^b2*...*2^bk = 2^(b2+...+bk).

The 5 known Fermat primes are 2^1+1, 2^2+1, 2^4+1, 2^8+1, 2^16+1.
This corresponds to possible values 1, 2, 4, 8, 16 of b2 to bk.
If there is a 6th Fermat prime then it is at least
2^(2^33)+1 = 2^8589934592+1.

nrp(2^m) is the number of x values with phi(x) = 2^m.
So nrp(2^m) is the number of ways to get either
2^m = 2^(b1-1 + b2+...+bk) implying m = b1-1 + b2+...+bk,
or 2^m = 2^(b2+...+bk) implying m = b2+...+bk,
with the above Fermat exponent conditions on b1 to bk.
Every integer from 0 to 31 can be written in exactly one way as a sum of
distinct members of {1, 2, 4, 8, 16}. Combine this with the free b1 in 2^b1,
and it follows that nrp(2^m) = m+2 for each m from 1 to 31, because for these
m values there is exactly one possible x for each b1 from 0 to m+1.

For m = 32 there is no possible x value for b1=0 or b1=1, so nrp(2^32) = 32.
If we assume there are no more Fermat primes then for any m >= 32, there
is only a possible x value for each b1 from m-30 to m+1, so:
nrp(2^m) = m+2, for m = 1..31
= 32, for m >= 32.
If all Fermat numbers had been primes then nrp(2^m) = m+2 would always hold.
With the known composite Fermat numbers below 2^(2^33)+1, we can say for sure
nrp(2^m) = 32, for 32 <= m < 2^33.

***

 

 

 

Records   |  Conjectures  |  Problems  |  Puzzles