2017-01-16, 22:53 | #1 |
Jan 2017
1_{16} 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 |
Jun 2003
5,179 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 |
Dec 2012
The Netherlands
2·3·293 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<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? |
2017-01-18, 01:41 | #4 |
"Matthew Anderson"
Dec 2010
Oregon, USA
953 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 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
A useful function. | JM Montolio A | Miscellaneous Math | 28 | 2018-03-08 14:29 |
Fun with partition function | Batalov | And now for something completely different | 24 | 2018-02-27 17:03 |
Gamma function | Calvin Culus | Analysis & Analytic Number Theory | 6 | 2010-12-23 22:18 |
Solve for mod function | flouran | Miscellaneous Math | 23 | 2009-01-04 20:03 |
Quick mod function ? | dsouza123 | Math | 16 | 2004-03-04 13:57 |