Well, divides 6, so there are also solutions other than powers of 2.
Hi everyone,
So i have the following question....
Determine all integers n for which φ(n) is a divisor of n.
Thinking about it logically, I think that the answer is going to be all the powers of 2?
I cant really work out how to set this in some kind of proof/definitive form?
Any ideas?
Thanks
A way to prove that is by using the following property of the Euler function :
for all primes p and where k>1.
Now note that 2 is prime, so that
.
This number is a divisor of .
I don't know yet how to find other numbers satisfying that property...
EDIT:
You can use the identity
.
If the only prime divisor of n is 2, then clearly which is a divisor of n.
Similarly, if the prime divisors of n are just 2 and 3, so where k is nonzero, then
.
This argument does not seem to work when using other primes, but I'm not sure
Ah, I've almost figured it out.
Let's try and prove it:
with .
The implication from right to left is easy: I've sort of shown it above already.
For the other implication, note that is even for .
Hence, since , n must be even, so write where is odd.
Now note using multiplicativity of . Hence we have
.
Write R as product of primes
. Then we have
Hence
.
Now assume that to find
. This implies and thus for some b greater than or equal to zero.
I'm not sure why we have that r=1. This remains to be proven, but I'm pretty sure this is the idea.