Finding all integers (>0) such that the Euler-Phi function = 8

**Timbuk2**

Find all integers n, where n>0, such that [latex]\phi(n) = 8[/latex].

[latex]\phi(n)[/latex] is the number of integers between 1 and n that relatively prime to n.

I'm not sure where to start! You don't have to post up a whole solution or anything, I just need a hint of where to go with this.

Is there a way of doing this without listing a whole pile of integers and seeing which ones work? It nearly sounds like I'd need to write a computer program to do this

Thanks

Fremen

Try it with n = 3 and n=4 and see if you can spot a pattern, maybe

**Timbuk2**

Thanks for the answer! I noticed that using both n=3 and n=4 gave 2 as a result. I continued from 3 up to 14, just to see if I noticed anything. I noticed that some results were repeated. To help spot a pattern, I drew a sort of table.

phi(n) =
2 4 6
3 5 7
4 8 9
6 10 14

Which is interesting (it may be completely irrelevant though, I'm just tricking around to see if I notice anything) as the third row is two times the first row.

I'll continue using n values past 14 - I'm sure something will click! I feel like I'm not far off!

FoxT

From the wording of your post it looks like you don't need to take the pure math approach - If this is true then you could write a computer program, or use excel. The phi function bounces around a lot. So for example if you find some number n such that phi (n)=8, there may well be larger numbers for which phi(n) is 8 also. How do you know when to stop?

One way to proceed would be to identify an upper limit - ie some number k such that phi(x)>8, for all x>=k then use a computer to find phi(n) for all n <=k.

Phi function is also known as the euler totient.... the wikipedia article on it has some stuff you may find useful.

FoxT

Your table looks OK - but you still need to know when to stop!

**Timbuk2**

Sorry I should have stated - it is a pure maths based solution that I am looking for, ideally!

I continued the table, so I now have n = 3,4,....,26. So far I have these values for n that give phi(n) = 8
15,16,20,24. I know there are more, but I'm not sure how to get them. The more I expanded my table, the more confused I became as there isn't an obvious pattern (not one that I can see anyway).

How can I calculate the upper limit, k?

Fremen

Ah crap, sorry, I phrased that wrong.

Sometimes if you can make a difficult problem simpler by considering a different case. You use the insight you get from solving the easy problem to solve the hard one.

Try solving the problem for phi(n) = 2 (really easy), phi(n) = 3, and phi(n) = 4. I haven't done it myself, but this is almost certainly the way to approach the problem.

**Timbuk2**

Fremen wrote: »

Ah crap, sorry, I phrased that wrong.

Sometimes if you can make a difficult problem simpler by considering a different case. You use the insight you get from solving the easy problem to solve the hard one.

Try solving the problem for phi(n) = 2 (really easy), phi(n) = 3, and phi(n) = 4. I haven't done it myself, but this is almost certainly the way to approach the problem.

Oh yea! That makes perfect sense! I'll get on that now and post how I got on (or more likely, post because I'm stuck! :P)

Thanks again!

**Timbuk2**

Is there a way of determining how many values there are?

I tried solving phi(n)=2, which gave me n=3,4,6 as possible results (there may be more).

phi(n) is even for n>=3, so I got phi(n)=4, which gave me n=5,8,10,12

Still haven't noticed anything yet (I will eventually, I am determined to figure this out!). I have sort of noticed that if I am solving for phi(n)=k, then phi(k+1) will give me a result that satisfies the equation. I haven't gone through enough values yet, but I have a suspicion this is only true if k+1 is prime (e.g. solving phi(n) = 2, phi(3) will give me 2).

Fremen

Try thinking about how phi works on primes first. Then think about how it works on squares of primes, and on numbers which are the product of exactly two primes. Then cubes of primes and so on.

I still haven't done it, but if you're still stuck tomorrow I'll go through it properly with a pen and paper.

**Timbuk2**

Thanks! There's no need to go to any trouble doing it out or anything, I'll eventually get it! Sure the harder I try to solve it the more I'll understand it when I do!

You've given me more than enough help to be able to do something with it! I think the fact that [latex]\phi(p^\alpha) = p^{\alpha-1}(p-1)[/latex], where p is some prime, needs to be used, which is what I think you were advising me to consider in your post. Similarly, [latex]\phi(mn) = \phi(m)\phi(n)[/latex], but I think m and n need to be relatively prime, but if m and n are both prime they have to be relatively prime (unless they are equivalent)

FoxT

you are right,

, only if gcd(m,n) = 1.

here is another property of phi:

if n is expressed as the product of primes (or powers of primess as follows) (note this factorisation is always unique for all n)
where each pi is a distinct prime, then
This last formula is an Euler product and is often written in the equivalent form (multiplying top and bottom by )
with the product ranging only over the distinct primes p dividing n.
Computing example


I have been mulling over this myself . For me the tough part of the problem is - how do you find n such that phi(k)>8 for all k>n. I know the answer for n=8, but dont know how to attack this in general.

rjt

FoxT wrote: »

you are right,

, only if gcd(m,n) = 1.

here is another property of phi:

if n is expressed as the product of primes (or powers of primess as follows) (note this factorisation is always unique for all n)
where each pi is a distinct prime, then
This last formula is an Euler product and is often written in the equivalent form (multiplying top and bottom by )
with the product ranging only over the distinct primes p dividing n.
Computing example


I have been mulling over this myself . For me the tough part of the problem is - how do you find n such that phi(k)>8 for all k>n. I know the answer for n=8, but dont know how to attack this in general.

Certainly, for small values (like 8) it isn't too hard to handle by case analysis using the expression for phi you gave. But I don't think there is a general closed form. See: http://oeis.org/A006511

FoxT

I agree, there is not a closed form, but there are upper & lower bounds.

upper bound - phi (n) <= (n-1) ( obvious enough)


EDIT:

Lower bounds: phi(n)>=1/2 sqrt(n)

Fremen

My first instinct was to say that phi(23) or phi of any number greater than 23 couldn't be less than 8 since 23 is the ninth prime number, and any number above that must be at least relatively prime to (blah...).

The (blah...) part doesn't quite work, but I guess you might be able to force it to work using (durr).

durr being something I can't figure out for the moment.

seandoiler

Fremen wrote: »

My first instinct was to say that phi(23) or phi of any number greater than 23 couldn't be less than 8 since 23 is the ninth prime number, and any number above that must be at least relatively prime to (blah...).

The (blah...) part doesn't quite work, but I guess you might be able to force it to work using (durr).

durr being something I can't figure out for the moment.

but isn't phi(30)=8? or am i mistaken?

red_fox

My go:

n can't have a prime factor > 7 as if it did then for p prime >7 we would have phi(n)=(p-1)m >10m > 8 (some integer m).

so any n is of the form 2^{a_2}3^{a_3}5^{a_5}7^{a_7}, and we can find individual bounds of a_7 \leq 1, a_5 \leq 1, a_3 \leq 2, a_2 \leq 4 when n is a prime power. Also we note that n can't be divisible by 3x7 or 5x7 or 2x2x7. That can be optimised more but so far it's a bound of 2^4 \times 3^2 \times 5 = 720, maybe that can be brought down to 60 or 90 but I haven't thought about it, this is somewhat redundant because:

Finally n=2^{a_2} 3^{a_3} 5^{a_5} since if 7 divides n then 6 divides phi(n). Which leaves 30 possible cases (a_2 =0,1,2,3,4 a_3=0,1,2 a_5 = 0,1) which can be checked by hand (or further optimisation would bring number that down; both a better upper bound and introduce a lower bound better than 0 )

Sorry for the lack of LaTeX and any possible errors, I was in a rush.

Spoiler covers my details but roughly find a bound by looking at the prime factorization of n and what that tells you about phi(n), and then enumerate cases of which phi(n) could be 8 and check by hand.

Edit: After FoxT's post I should clarify that by "possible prime factorizations of n" I was thinking of n as any number each having a different factorization. i.e. consider the factorizations. I now look foolish! Edited above for clarity.

FoxT

The evolution continues....


Fundamental theorem of arithmetic states that every number can be decomposed into a UNIQUE set of factors which are either prime, or powers of primes. So , every number can be written as (P1^k1)(P2^k2)(P3^k3).....(Pn^kn)

Now, phi of (P1^k1)(P2^k2)(P3^k3).....(Pn^kn) = phi(P1^k1)phi(P2^k2).....phi(Pn^kn)


We are looking for phi(n) = 8, so each of phi(P1^k1), phi(P2^k2)....phi(pn^kn) must be a factor of 8.


Factors of 8 are 1,2,4,8. So – list every number of the form p^k such that phi(p^k) is a factor of 8.


This simplifies the problem greatly – for example finding all P^k which have a phi of 8 is much simpler than finding all numbers which have a phi(8). You are dealing in all cases with primes less than 7, for a start, because phi(7) = 6 and 6 is not a factor of 8, and phi(p)=p-1 for all primes.


One minor point to take some care on - the multiplicative property above assumes that gcd (Pa^a,Pb^b) = 1. so be careful when combining say phi(2) and phi(2^2)...multiplicative property wont hold for these.

I expect you can move the plot along from there yourself!

PS - a nice primer on the Phi (or totient, as it is sometimes called) function is to be found in "Elementary Number Theory" David M Burton, ISBN 0-697-06896-X

**Timbuk2**

Thanks for the answers and the help, that's brilliant!

hey367

there is a general formula for Phi n, you can deduce that for any prime factor p of n, p-1 divides Phi(n)=8, 8 has only for divisors 1,2,4,8 those gives p can be 2,3 or 5 so n is 2,3,5 raised to some powers which can be zero
by considering the cases you find n=2.3.5 or 2.2.2.3 or 2.2.5 or 3.5 or 2.2.2.2
(Start from 5 the power of 5 is at most 1 otherwise phi n is divisible by 5....similarly for 3)

so it has five solutions 15,16,20,24 and 30 there is no any other solution
good luck

hey367

similarly you can solve Phi(n)=6,12,10 or 100 by the same method.
for some of them it may be more complicated but this is the best way to solve.