1. ## 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))

2. 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.

3. 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.

4. 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
.
.
.

5. 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.

6. 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

7. 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.

8. 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).