mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2017-01-16, 22:53   #1
rula
 
Jan 2017

1 Posts
Default 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
rula is offline   Reply With Quote
Old 2017-01-17, 03:49   #2
axn
 
axn's Avatar
 
Jun 2003

3·112·13 Posts
Default

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...
axn is online now   Reply With Quote
Old 2017-01-17, 09:56   #3
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

145510 Posts
Default

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?
Nick is online now   Reply With Quote
Old 2017-01-18, 01:41   #4
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

22·151 Posts
Default

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
MattcAnderson is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 10:59.

Thu Oct 29 10:59:40 UTC 2020 up 49 days, 8:10, 1 user, load averages: 1.00, 1.37, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.