So, I was given this question by a friend of mine, and i thought i would share it with you guys.

For n > 4, what properties does n have, should they even exist, that satisfy the relationship n = phi(n) + d(n)

where phi is Euler's phi and d is the number of numbers that divide n.

mind you, I was given this question as something to think about, not as an exercise. There is not any one right answer, just some interesting conclusions you can draw about these numbers.

Anyway, thought you cool kids would like it

## n=phi(n)+d(n), not a true puzzle

**Moderators:** gmalivuk, Moderators General, Prelates

- peri_renna
**Posts:**85**Joined:**Wed Sep 20, 2006 2:52 pm UTC-
**Contact:**

- Yakk
- Poster with most posts but no title.
**Posts:**11109**Joined:**Sat Jan 27, 2007 7:27 pm UTC**Location:**E pur si muove

Phi(N) has a nice way to express it's value.

So does D(N).

Phi(N) = product(p prime, k_p>1 maximal integer, p^k_p|N)( (p-1)p^(k_p-1) )

D(N) can be expressed as a combinatorial function based off of the above k_p's.

So, Phi(N) is in a way "close" to N. Those -1s determine how big the combinatorial expression of D(N) has to be.

So does D(N).

Phi(N) = product(p prime, k_p>1 maximal integer, p^k_p|N)( (p-1)p^(k_p-1) )

D(N) can be expressed as a combinatorial function based off of the above k_p's.

So, Phi(N) is in a way "close" to N. Those -1s determine how big the combinatorial expression of D(N) has to be.

- 3.14159265...
- Irrational (?)
**Posts:**2413**Joined:**Thu Jan 18, 2007 12:05 am UTC**Location:**Ajax, Canada

suppose n=phi(n) + d(n)

Find the prime decomposition of n = 2^c*(3)^d*....(p)^z,

n=phi(n) + f(n) where f(n) are the numbers that have at least one factor in common with n.

Then d(n) must equal f(n). So any number that has at least one prime factor in common must also have all its prime factors in n.

Now let i be the smallest prime in the prime decomposition of n that such i is greater than 2

now if there are any other unique prime factor greater other than 2 and i, then 2^(a+1)*i<n and is in f(n) but is not in d(n) therefore:

f(n)>phi(n)

since: phi(n)+f(n)=n

then: phi(n)+d(n)<n

So n can not have any more than one unique prime factor grater than 2

Now this means that that n = 2^a*(p)^d for some integers a and d, and a prime p

"The best times in life are the ones when you can genuinely add a "Bwa" to your "ha""- Chris Hastings

- 3.14159265...
- Irrational (?)
**Posts:**2413**Joined:**Thu Jan 18, 2007 12:05 am UTC**Location:**Ajax, Canada

n = \sum_{d | n, d > 0} \phi(d).

The theorem can be proven by considering all the fractions i/n for i = 1, 2, ... , n, and writing them in reduced form.

Otherwise, its pretty clear that a number satisfying n = phi(n) + d(n)

must have the property that

Only one proper divisor d of n can have phi(d) > 1, and in particular it must satisfy phi(d) = 2.

Now, the only numbers satisfying

phi(d) = 2 are d = 3 and d = 4,

and the only ones satisfying

phi(d) = 1 are d = 1 and d = 2.

So, the only numbers that can possibly work are those with proper divisors 2,3 or proper divisors 2,4.

Therefore, we have a VERY limited set of solutions: in particular, 8 and 9 are the only values of n that work!

To contrast the above post, we can note that 16 does not work, since phi(16) = 8 and d(16) = 5.

- 3.14159265...
- Irrational (?)
**Posts:**2413**Joined:**Thu Jan 18, 2007 12:05 am UTC**Location:**Ajax, Canada

You didn't contrast anything, I didn't make a "If and only If" statement, just a "only If" statement.

I like your solution.

EDIT: I just realized where I had gone wrong, I forgot that 1 is also a divisor.

I like your solution.

EDIT: I just realized where I had gone wrong, I forgot that 1 is also a divisor.

"The best times in life are the ones when you can genuinely add a "Bwa" to your "ha""- Chris Hastings

### Who is online

Users browsing this forum: No registered users and 8 guests