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

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

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

Postby Sygnon » Sat Apr 28, 2007 8:31 pm UTC

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

User avatar
peri_renna
Posts: 85
Joined: Wed Sep 20, 2006 2:52 pm UTC
Contact:

Postby peri_renna » Sat Apr 28, 2007 11:12 pm UTC

Do we include the number itself in d(n)?

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

Postby Yakk » Sat Apr 28, 2007 11:19 pm UTC

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.

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

Postby 3.14159265... » Sat Apr 28, 2007 11:36 pm UTC

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

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

Postby 3.14159265... » Mon May 14, 2007 10:06 pm UTC

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

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

Postby Sygnon » Wed May 16, 2007 8:00 am UTC

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

Postby thobel » Thu May 31, 2007 6:51 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.

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

Postby 3.14159265... » Thu May 31, 2007 7:51 pm UTC

You didn't contrast anything, I didn't make a "If and only If" statement, just a "only If" statement.
I like your solution. :D

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

Postby thobel » Thu May 31, 2007 8:39 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 4 guests