Go Back > New To GIMPS? Start Here! > Homework Help

Thread Tools
Old 2021-02-13, 12:59   #1
chao wu
Feb 2021

1 Posts
Default 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
chao wu is offline   Reply With Quote
Old 2021-02-13, 19:08   #2
Nick's Avatar
Dec 2012
The Netherlands

22·3·5·29 Posts

You could start by thinking about which positive integers k have ϕ(k)=2ⁿ.
Nick is offline   Reply With Quote
Old 2021-02-13, 19:53   #3
Batalov's Avatar
Mar 2008

23×5×239 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).
Batalov is offline   Reply With Quote
Old 2021-02-13, 21:46   #4
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

5D516 Posts

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.

Last fiddled with by R. Gerbicz on 2021-02-13 at 21:47
R. Gerbicz is offline   Reply With Quote

Thread Tools

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

All times are UTC. The time now is 03:21.

Sat Oct 16 03:21:17 UTC 2021 up 84 days, 21:50, 0 users, load averages: 1.30, 1.06, 1.06

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.