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

- - **phi function**
(*https://www.mersenneforum.org/showthread.php?t=21947*)

phi functioncan 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 |

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

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.