# Phi(n)

• Mar 27th 2007, 12:35 AM
Ideasman
Phi(n)
Let phi(n) = # of pos. integers < n that's relatively prime to n.

1.) Theorem: phi(n) | n if and only if _______

a.) Show three numbers that will satisfy phi(n) | n.

b.) Fill in the above blank.

c.) Prove this theorem.

-------------

n is prime iff phi(n) = n - 1

phi(n) is a multiplicative func.... that is, phi(n) = phi((p_1)^(a_1)*phi((p_2)^(a_2)*...*phi((p_k)^(a_k )

A formula for phi(n) ...

n*(1 - 1/(p_1))*(1 - 1/(p_2))* ... *(1 - 1/(p_k))
• Mar 27th 2007, 10:07 AM
ThePerfectHacker
Quote:

Originally Posted by Ideasman
Let phi(n) = # of pos. integers < n that's relatively prime to n.

1.) Theorem: phi(n) | n if and only if _______

Are you sure this has an easy answer to it. It looks a little too extreme for me.

I would guess the following....

Conjecture: All the positive integers described above are:
1,2, 2^n, 2^a*3^b
Where n,a,b are positive integers.

I leave it to you to show that phi(n) will divide n.
• Mar 27th 2007, 05:10 PM
Ideasman
According to my prof. this is not correct TPH. I have to apparently look at some values. I am trying it again now and will see what I can come up with. If you have any suggestions please let me know.
• Mar 27th 2007, 07:15 PM
Ideasman
Okay, I did what my prof. suggested but it didn't (seem) to help:

When n = 1, phi(n) = 1

n = 2, phi(n) = 1

Below will be n = the first number and phi(n) will = the second number.

3...2
4...2
5...4
6...2
7...6
8...4
9...6
10...4
11...10
12...4
13...12
14...6
15...8
16...8
17...16
18...6
19...18
20...8
21...12
22...10
23...22
24...8
25...20
26...12
27...18
28...12
29...28
30...8
31...30
32...16
33...20
34...16
35...24
36...12
37...36
38...18
39...24
40...16
41...40
42...12
43...42
44...20
45...24
46...22
47...46
48...16
49...42
50...20
.
.
.
• Mar 27th 2007, 07:23 PM
ThePerfectHacker
Actually I think I am correct. I managed to proof it. :)

I will try to post a proof, it is a little long.
And LaTeX is down, I will modify this post with my first LaTeX image, for you to read.
• Mar 27th 2007, 07:25 PM
Ideasman
Quote:

Originally Posted by ThePerfectHacker
Actually I think I am correct. I managed to proof it. :)

I will try to post a proof, it is a little long.
And LaTeX is down, I will modify this post with my first LaTeX image, for you to read.

Haha, smarter than a professsor..

It was also suggested that I list the numbers and break them into prime factorization
• Mar 27th 2007, 07:43 PM
ThePerfectHacker
Quote:

Originally Posted by Ideasman
Haha, smarter than a professsor..

It was also suggested that I list the numbers and break them into prime factorization

Here is my first LaTeX post.
• Mar 27th 2007, 07:47 PM
ThePerfectHacker
Continued.

Note, when I show that r=3.

That means,

n=2^a*3^b for n>2 exactly what I said.

(This is a necesary condition. I assume that it is also sufficient. But that is easy if it is really true. I leave the easy part to thee).