Thread: Euler Phi Funcs.

1.) Determine all the pos. int. n such that Phi(n) has the following values. Make sure that you have proved that you found all the soln's.

a.) 1
b.) 2
c.) 3
d.) 4

2.) Find all pos int. n shut that Phi(n) = 6. Again, make sure you've proven that you found all solutions.

3.) For which integers n (positive) is Phi(n) div. by 4?

Hello, Ideasman!

This is not an easy set of problems . . . I have #2 solved (I think).

Given a positive integer N, φ(N) is the number of integers less than N
. . which are relatively prime to N. .(1 is included in the count.)

If the prime factorization of N is: .N .= .(p^a)(q^b)(r^c) ...

. . then: .φ(N) .= .p^{a-1}·(p - 1)·q^{b-1}·(q - 1)·r^{c-1}·(r - 1) ...

2) Find all pos int. n such that: φ(n) = 6.

6 .= .1·6 .= .7^0·(7 - 1) . → , n = 7

6 .= .1·1·1·6 .= .2^0·(2 - 1)·7^0·(7 - 1) . → . n = 14

6 .= .3·2 .= .3^1·(3 - 1) . → . n = 9

6 .= .1·1·3·2 .= .2^0·(2-1)·3^1·(3 - 2) . → . n = 18

3) For which integers n is φ(n) div. by 4?

I'm still working on this one ... don't know if I'll ever finish it.

If n is of the form: .(2^m)·(p) .for m > 3
. . then: .φ(n) .= .2^{m-1}·(q) .is divisible by 4.

If n has a prime factor of the form: .p .= .4m + 1,
. . then: .φ(n) .= .p^{n-1}·(4m) ... . is divisible by 4.

The list seems to go on and on . . .