Let phi(n) be the Euler phi-function which is defined to be the number
of positive integers not exceeding n and that are relatively prime to
n.
Find all positive integers n such that phi(n)=6

Hello fmunshi:

Thanks for the interesting question.

I used Maple (a mathematical programing language to find all positive
integers n such that phi(n) = 6. Fortunately, Maple has a function
just for this in its number theory package. The invphi function
"returns a increasing list of integers [m1, m2, ..., mk] such that
phi(mi) = n for i from 1 to k."

The result of the call

invphi(6)

is 

[7, 9, 14, 18]

If we want to verify this, we can use the phi function on the first
100 positive integers to get:

[1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12,
10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24,
16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24,
36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44, 24, 70, 24, 72,
36, 40, 36, 60, 24, 78, 32, 54, 40, 82, 24, 64, 42, 56, 40, 88, 24,
72, 44, 60, 46, 72, 32, 96, 42, 60, 40]

As you can see, the 6s appear in the 7th, 9th, 14th, and 18th
positions.

I hope this answers your question. Please ask for clarification if you
need it.

Thanks. 

websearcher-ga


Search Strategy: none, but you could try:

euler phi
://www.google.ca/search?q=euler+phi&ie=ISO-8859-1&hl=en&meta=

---

Clarification of Answer by websearcher-ga on 07 Apr 2003 12:38 PDT

Just to clarify, the relatively prime values for each of those four numbers are:

7 -- 1, 2, 3, 4, 5, 6
9 -- 1, 2, 4, 5, 7, 8
14 -- 1, 3, 5, 9, 11, 13
18 -- 1, 5, 7, 11, 13, 17

websearcher-ga

---

Request for Answer Clarification by fmunshi-ga on 07 Apr 2003 13:26 PDT

is there anyway to do this without the help of a computer program??

---

Clarification of Answer by websearcher-ga on 07 Apr 2003 13:58 PDT

Hello fmunshi:

The only way I could find to do this other than by a computer program
is by starting off at phi(6+1) and doing the subsequent numbers by
hand. Once you get to phi(30) or so, you'll see that the value of
phi(n) is never going to be < 10 again, so you can stop.

An interesting formula for computing phi(n) can be found at 

PlanetMath: Euler phi-function
URL: http://planetmath.org/encyclopedia/EulerPhifunction.html

This formula takes n and multiplies it by the product of a function of
the prime factors of n. From this formula, it is east to see that as n
gets higher, so will phi(n) - confirming that you can stop checking
for phi(n)=6 after you've tried a certain amount of the way.

Another useful page is:

Totient Function - from MathWorld
URL: http://mathworld.wolfram.com/TotientFunction.html

I hope this helps. 

websearcher-ga

Hello fmunshi,

There is a way to solve this problem without the aid of a computer
program such as Maple. As websearcher said (or should have), Mathworld
is very useful, two pages in particular:

Multiplicative Function: 
http://mathworld.wolfram.com/MultiplicativeFunction.html
Euler Phi (Totient) Function: 
http://mathworld.wolfram.com/TotientFunction.html

We will be using two results
(a) The Euler phi function is multiplicative, that is
  phi(mn) = phi(m) * phi(n)
if m and n are relatively prime.
(b) phi( p^alpha ) = p^alpha - p^{alpha-1} = p^{alpha-1} * (p-1)

Using fact (a), we have that if n = p_1^{a_1} * p_2^{a_2} * ... *
p_k^{a_k} (p_i prime, a_i are the exponents) is the prime
factorization of n,

phi(n) = phi( p_1^{a_1} ) * phi( p_2^{a_2} ) * ... * phi( p_k^{a_k} ).

Therefore, if phi(n) = 6, each phi( p_i^{a_i} ) has to be a factor of
6. Using fact (b), the only phi( p^alpha ) equal to 1, 2, 3, or 6 are

phi( 2 )   = 1,
phi( 3 )   = 2,
phi( 2^2 ) = 2,
phi( 7 )   = 6, and
phi( 3^2 ) = 6.

Note that there is no number n' for which phi(n') = 3. Now, the only
ways of combining these are:

(i) using the prime powers themselves,
i.e. phi( 7 ) = phi( 3^2 ) = 6,
and (ii) multiplying the prime powers by 2, because phi(2) = 1,
i.e. phi( 2*7 ) = phi( 2*3^2 ) = 6.

The result is, as stated by webmaster, that phi(7) = phi(9) = phi(14)
= phi(18) = 6, and these are the only such numbers.

- kaif.

Correction: change webmaster to websearcher.

Addenda:
This is a general method that should work if you want to solve phi(n)
= k for any k. Presumably Maple does something of this sort.

websearcher's comment,
  "Once you get to phi(30) or so, you'll see that the value of phi(n)
is never going to be < 10 again, so you can stop",
is true but unjustified. There *are* various lower bounds on phi(n),
for example
  phi(n) > sqrt{n} / 2.
By this method, you would have to search up to 12^2 = 144, which is a
tad tedious. There are certainly better bounds, and the "guess that it
won't go lower than 10 again" method is one of them.

And yeah, Google search strategy? Didn't seem to work but
  Euler phi function, inverse, (having found out about invphi) invphi,
etc.
might lead to something.

A general Google search on "Integer Sequences" does bring up the
Encyclopedia of Integer Sequences at
  http://www.research.att.com/~njas/sequences/

A search on "math" (how helpful!) indeed brings up Mathworld
  http://mathworld.wolfram.com/
as the tenth result.

So, I guess Google doesn't solve math problems yet.

- kaif.