Results 1 to 5 of 5

Math Help - Find all positive integers n such that euler's phi equals 6

  1. #1
    Junior Member
    Joined
    Feb 2010
    From
    New Jersey
    Posts
    73

    Find all positive integers n such that euler's phi equals 6

    I haven't the faintest idea how to do this. The homework question reads:

    Find all positive integer n such that \varphi(n) = 6. Briefly explain why.

    I know that:
    1. if n is prime, then \varphi(n)=n-1.
    2. if n=pq, where p and q are distinct primes, then \varphi(n)=(p-1)(q-1).
    3. if n=p^e then \varphi(n)=p^e-p^{e-1}.
    4. if n=p_1^{e_1}, p_2^{e_2},...p_r^{e_r}, where p_i are distinct primes, then \varphi(n)=N(1-1/p_1)(1-1/p_2)...(1-1/p_r) (which is really just a generalization of step 3).

    I can't find any other info about phi(n) in my notes or in the chapters we've done this semester.

    I only come up with the answer n=7. But the question wants all values of n which result in \varphi(n) = 6.

    How do I do this please?
    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Find all positive integers n such that euler's phi equals 6

    Quote Originally Posted by MSUMathStdnt View Post
    I haven't the faintest idea how to do this. The homework question reads:

    Find all positive integer n such that \varphi(n) = 6. Briefly explain why.


    I know that:
    1. if n is prime, then \varphi(n)=n-1.
    2. if n=pq, where p and q are distinct primes, then \varphi(n)=(p-1)(q-1).
    3. if n=p^e then \varphi(n)=p^e-p^{e-1}.
    4. if n=p_1^{e_1}, p_2^{e_2},...p_r^{e_r}, where p_i are distinct primes, then \varphi(n)=N(1-1/p_1)(1-1/p_2)...(1-1/p_r) (which is really just a generalization of step 3).
    I can't find any other info about phi(n) in my notes or in the chapters we've done this semester.

    I only come up with the answer n=7. But the question wants all values of n which result in \varphi(n) = 6.

    How do I do this please?
    Thanks
    Let's start from definition...

    \varphi(n)= n\ \prod_{p|n} \frac{p-1}{p} (1)

    If \varphi(n)=6 then from (1) it is evident that n=7 and n=14 both satisfy the requirement. For n<7 but a simple exaustive search shows that there are no n<7 satisfying the requirement. For n>7 we can observe that n=9 satisfies the requirement and the same is for n=18. No possibilities for n>18...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    From
    New Jersey
    Posts
    73

    Re: Find all positive integers n such that euler's phi equals 6

    How did you find that n=9? There isn't any obvious algebra which gets me to that answer. What do you mean by it is "evident" that n=7 (I agree) and that we can "observe" that n=9?
    Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Find all positive integers n such that euler's phi equals 6

    Quote Originally Posted by MSUMathStdnt View Post
    How did you find that n=9? There isn't any obvious algebra which gets me to that answer. What do you mean by it is "evident" that n=7 (I agree) and that we can "observe" that n=9?
    Thanks.
    Let's write again...

    \varphi (n)= n\ \prod_{p|n} \frac{p-1}{p} (1)

    Two properties are evident...

    a) if n prime then \varphi(n)=n-1...

    b) if n odd then \varphi(2 n)= \varphi(n) ...

    On the basis of a) and b) You find immediately that for n=7 and n=14 is \varphi(n)=6. In order to find other n satisfying the equation You can observe that 6=2 x 3, so that on the basis of (1) this n must contain 3. Effectively n=9 satisfies the reqirement and because 9 is odd, also 18 does...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: Find all positive integers n such that euler's phi equals 6

    another way is to use the multiplicative property of φ, that is, if:

    n = p_1^{k_1}p_2^{k_2}\dots p_r^{k_r} where the p_i are distinct primes, then

    \varphi(n) = \varphi(p_1^{k_1})\varphi(p_2^{k_2})\dots \varphi(p_r^{k_r})

    = (p_1 - 1)p_1^{k_1 - 1}(p_2 - 1)p_2^{k_2 - 1}\dots(p_r - 1)p_r^{k_r-1}.

    now if φ(n) = 6, and p is a prime dividing n, then p^k|n for some k.

    if p^3|n, then φ(p^3) divides φ(n) = 6. but φ(p^3) = (p-1)p^2, and 6 is square-free.

    so n can only have single primes, or squares of primes in its factorization.

    suppose p|n, but p^2∤n. then p-1|6, so p can only be 2,3,or 7.

    if p^2|n then (p-1)p|6, so p can only be 2, or 3.

    let's look at the last case first. suppose p^2|n, so p = 2 or 3. if p = 2, then n = 4m, for some m co-prime to 2. so 6 = φ(n) = φ(4m) = φ(4)φ(m) = 2φ(m), so φ(m) = 3.

    but there are no positive integers m for which φ(m) = 3. because if a prime q|m, then q-1|3, and hence q = 2. but φ(2) = 1, and φ(2^t) = 2^(t-1) which certainly does not divide 3 for t > 1.

    so n is not a multiple of 4. thus if p^2|n, p = 3 is the only possibility. so n = 9m, for some m co-prime to 3. thus 6 = φ(n) = φ(9)φ(m) = 6φ(m), which means that φ(m) = 1, so m = 1 or 2. this means that if n is not square-free, then n = 9 or 18.

    so now we consider when n IS square-free: so n = 2,3,7,2*3,2*7,or3*7. that's only 6 cases to check:

    φ(2) = 1.
    φ(3) = 2.
    φ(7) = 6.
    φ(2*3) = φ(2)φ(3) = 1*2 = 2.
    φ(2*7) = φ(2)φ(7) = 1*6 = 6.
    φ(3*7) = φ(3)φ(7) = 2*6 = 12.

    this gives us n = 7,9,14 and 18 as the only possibilities.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 3rd 2011, 03:40 AM
  2. find triples of positive integers.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 17th 2009, 09:02 AM
  3. Find positive integers
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: April 22nd 2009, 02:37 PM
  4. Find all positive integers such that...?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 20th 2008, 11:20 AM
  5. Replies: 2
    Last Post: July 5th 2005, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum