mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Homework Help (https://www.mersenneforum.org/forumdisplay.php?f=78)
-   -   Solve phi(m^n+n)=2^n over positive integers? (https://www.mersenneforum.org/showthread.php?t=26492)

 chao wu 2021-02-13 12:59

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?

[color=red][b]MODERATOR NOTE:[/b] Moved to Homework Help.[/color]

 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 [URL="https://en.wikipedia.org/wiki/How_to_Solve_It"]How to Solve It[/URL].
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.

 All times are UTC. The time now is 13:46.