phi function
 

can any one help

prove that the integer n>1 i s prime if and only if

phi(n) > n - (n)^1/2


where phi is Euler's phi function

This is incorrect. The correct condition is phi(n) = n-1

EDIT:- Or not. I suppose that condition works too. HINT. Assume that n is composite. What is the least number of integers that have a common factor with n.

Here is a little more detail to axn's hint.

If n is prime then \(\phi(n)=n-1>n-\sqrt{n}\) since n>1.

If n is not prime then n=km for some integers k,m with 1<k<n and 1<m<n.
At least one of k and m is greater than or equal to \(\sqrt{n}\) and we may choose the names so that \(k\geq\sqrt{n}\).
Now \(\phi(n)\) equals the number of integers in the list 0,1,2,,...,n-1 which have no factor in common with n.
How many numbers in the list are multiples of m?

Hopefully this helps with understanding of Euler phi function.

The Online Encyclopedia of Integer Sequences lists values of phi(n).
[URL]http://oeis.org/A000010[/URL]

Also, I like Wolfram as a reference

[URL]http://mathworld.wolfram.com/TotientFunction.html[/URL]

For example phi(6) = 2 because 1 and 5 are relatively prime to 6.

For what its worth.
Matt