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

11·421 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 offline   Reply With Quote
Old 2017-01-17, 09:56   #3
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

3·7·67 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

2×5×59 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 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

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.