Solve phi(m^n+n)=2^n over positive integers?

chao wu · 2021-02-13, 12:59

How to solve phi(m^n+n)=2^n over positive integers? Where both m and n are positive integers, and phi denotes the Euler function. We can find that (m,n)=(2,1), (3,1) or (5,1) are some examples of solutions. Can someone give me any hints for this problem?

MODERATOR NOTE: Moved to Homework Help.

Nick · 2021-02-13, 19:08

You could start by thinking about which positive integers k have ϕ(k)=2ⁿ.

Batalov · 2021-02-13, 19:53

This reminds me of the George Pólya book How to Solve It.
Everyone could do very well by reading it. (Some time in their life, I mean.)
Nick's suggestion fits the patterns Work backward, Eliminate possibilities, Consider special cases (or something like that, I am shooting from the hip).

R. Gerbicz · 2021-02-13, 21:46

If x is composite then we know:
c*x/log(log(x))<phi(x)<=x-sqrt(x), where c>0 is a constant [c=0.25 is good for all x>6].

ok, not very elegant to use these, though this is still elementary.
With this you can easily solve the problem, the remaining x=m^n+n prime case is very easy.

2021-02-13, 12:59	#1
chao wu Feb 2021 1 Posts	Solve phi(m^n+n)=2^n over positive integers? How to solve phi(m^n+n)=2^n over positive integers? Where both m and n are positive integers, and phi denotes the Euler function. We can find that (m,n)=(2,1), (3,1) or (5,1) are some examples of solutions. Can someone give me any hints for this problem? MODERATOR NOTE: Moved to Homework Help. Last fiddled with by Dr Sardonicus on 2021-02-13 at 14:21 Reason: As indicated

2021-02-13, 21:46	#4
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 2×7×103 Posts	If x is composite then we know: cx/log(log(x))<phi(x)<=x-sqrt(x), where c>0 is a constant [c=0.25 is good for all x>6]. ok, not very elegant to use these, though this is still elementary. With this you can easily solve the problem, the remaining x=m^n+n prime case is very easy. Last fiddled with by R. Gerbicz on 2021-02-13 at 21:47*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sums of a positive cube and a power of 2	enzocreti	enzocreti	6	2020-02-19 04:47
Fun with a false positive	Madpoo	Data	12	2016-06-29 19:00
another false positive?	ixfd64	Data	3	2016-03-14 22:11
positive LL test?	sixblueboxes	PrimeNet	90	2014-07-24 05:51
False positive?	Pi Rho	Lounge	4	2003-04-23 14:11

2021-02-13, 19:08	#2
Nick Dec 2012 The Netherlands 11001010000₂ Posts	You could start by thinking about which positive integers k have ϕ(k)=2ⁿ.

2021-02-13, 19:53	#3
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 246C₁₆ Posts	This reminds me of the George Pólya book How to Solve It. Everyone could do very well by reading it. (Some time in their life, I mean.) Nick's suggestion fits the patterns Work backward, Eliminate possibilities, Consider special cases (or something like that, I am shooting from the hip).