phi function

rula · 2017-01-16, 22:53

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).
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

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 43×127 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...

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Fun with partition function	Batalov	And now for something completely different	49	2022-08-04 12:08
A useful function.	JM Montolio A	Miscellaneous Math	28	2018-03-08 14:29
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

2017-01-17, 09:56	#3
Nick Dec 2012 The Netherlands 2×7×131 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
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 2³·149 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