mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Homework Help (https://www.mersenneforum.org/forumdisplay.php?f=78)

 rula 2017-01-16 22:53

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

 axn 2017-01-17 03:49

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.

 Nick 2017-01-17 09:56

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?

 MattcAnderson 2017-01-18 01:41

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

 All times are UTC. The time now is 16:50.