mersenneforum.org phi function
 Register FAQ Search Today's Posts Mark Forums Read

 2017-01-16, 22:53 #1 rula   Jan 2017 1 Posts 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
 2017-01-17, 03:49 #2 axn     Jun 2003 11·421 Posts 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. Last fiddled with by axn on 2017-01-17 at 03:58 Reason: thinking...
 2017-01-17, 09:56 #3 Nick     Dec 2012 The Netherlands 3·7·67 Posts 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
 2017-01-18, 01:41 #4 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 2×5×59 Posts Hopefully this helps with understanding of Euler phi function. The Online Encyclopedia of Integer Sequences lists values of phi(n). http://oeis.org/A000010 Also, I like Wolfram as a reference http://mathworld.wolfram.com/TotientFunction.html For example phi(6) = 2 because 1 and 5 are relatively prime to 6. For what its worth. Matt

 Similar Threads Thread Thread Starter Forum Replies Last Post JM Montolio A Miscellaneous Math 28 2018-03-08 14:29 Batalov And now for something completely different 24 2018-02-27 17:03 Calvin Culus Analysis & Analytic Number Theory 6 2010-12-23 22:18 flouran Miscellaneous Math 23 2009-01-04 20:03 dsouza123 Math 16 2004-03-04 13:57

All times are UTC. The time now is 15:37.

Sat Jul 4 15:37:50 UTC 2020 up 101 days, 13:10, 2 users, load averages: 1.93, 2.03, 2.29

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.