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

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Sygnon
Posts: 32
Joined: Tue Jan 23, 2007 1:47 am UTC
Contact:

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

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

peri_renna
Posts: 85
Joined: Wed Sep 20, 2006 2:52 pm UTC
Contact:
Do we include the number itself in d(n)?

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.

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
I'm just wondering, no one commented about this, did no one find it awsome?
"The best times in life are the ones when you can genuinely add a "Bwa" to your "ha""- Chris Hastings

Sygnon
Posts: 32
Joined: Tue Jan 23, 2007 1:47 am UTC
Contact:
man, i found that particularly rad. you did pretty much line for line what i did, but we diverged when you began to talk about the building up the prime factors of n (which after reading your post i thought was mega fucking rad), i played around to see if the residue systems of n would have any strange properties, but most of the conclusions were rather obvious so i put the problem down for a bit.

thobel
Posts: 19
Joined: Fri Nov 03, 2006 9:43 pm UTC
So, the question isn't that interesting in light of the following basic theorem:

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.
"The best times in life are the ones when you can genuinely add a "Bwa" to your "ha""- Chris Hastings

thobel
Posts: 19
Joined: Fri Nov 03, 2006 9:43 pm UTC
Ahh, very good then. If you exclude 1, you get a slightly larger set of solutions, but still quite finite .

Return to “Mathematics”

### Who is online

Users browsing this forum: No registered users and 8 guests