[math-fun] question
Can phi(n) divide n - 1, if n is not a prime? If n contains a power of a prime, p (the power being bigger than or equal to 2), then there's a contradiction, because phi(n) is divisible by p, but n-1 is not divisible by p. Also, n is not even, because n-1 would be odd, which cannot be divisible by phi(n) [unless n = 2 exactly]. Claim: if r and s are odd, then (r-1)(s-1) > 1/2 * rs. Consider (r-1)(s-1) = rs - (r+s) + 1 > rs/2 iff rs/2 + 1 > (r+s) Let r < s, then r+s < 2s. But if r >= 5, then rs/2 > 2s. So it is enough to show it for r = 3 (and r<s). Then we must show that 2(s-1) > 3/2 s, where s >= 5, but this is clear. Now we can build up (p1-1)(p2-1)(p3-1) > (p1*p2/2)*(p3-1) > p1*p2*p3/2, etc. So, for phi(n) to divide n - 1, since n does not contain a non-trivial power of a prime, n is of the form p1*p2*...*pn, where all of the pi's are odd. But then phi(n) > 1/2 * n, so it cannot divide n - 1. So for your original question, yes, I think so. -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of David Wilson Sent: Friday, December 11, 2009 1:46 PM To: math-fun Subject: [math-fun] question x == 1 (mod phi(x)) ==> x prime? (x >= 2) _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
----- Original Message ----- From: "Cordwell, William R" <wrcordw@sandia.gov> To: "'math-fun'" <math-fun@mailman.xmission.com> Sent: Friday, December 11, 2009 4:31 PM Subject: Re: [math-fun] question
Can phi(n) divide n - 1, if n is not a prime?
If n contains a power of a prime, p (the power being bigger than or equal to 2), then there's a contradiction, because phi(n) is divisible by p, but n-1 is not divisible by p.
Also, n is not even, because n-1 would be odd, which cannot be divisible by phi(n) [unless n = 2 exactly].
Claim: if r and s are odd, then (r-1)(s-1) > 1/2 * rs. Consider (r-1)(s-1) = rs - (r+s) + 1 > rs/2 iff rs/2 + 1 > (r+s) Let r < s, then r+s < 2s. But if r >= 5, then rs/2 > 2s. So it is enough to show it for r = 3 (and r<s). Then we must show that 2(s-1) > 3/2 s, where s >= 5, but this is clear.
Now we can build up (p1-1)(p2-1)(p3-1) > (p1*p2/2)*(p3-1) > p1*p2*p3/2, etc.
So, for phi(n) to divide n - 1, since n does not contain a non-trivial power of a prime, n is of the form p1*p2*...*pn, where all of the pi's are odd. But then phi(n) > 1/2 * n, so it cannot divide n - 1.
Not true. Take n = 105 = 3*5*7. Then phi(n) = 48 < 1/2 * n.
So for your original question, yes, I think so.
-----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of David Wilson Sent: Friday, December 11, 2009 1:46 PM To: math-fun Subject: [math-fun] question
x == 1 (mod phi(x)) ==> x prime? (x >= 2)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-------------------------------------------------------------------------------- No virus found in this incoming message. Checked by AVG - www.avg.com Version: 8.5.426 / Virus Database: 270.14.103/2558 - Release Date: 12/11/09 10:06:00
Oops... Thanks. -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of David Wilson Sent: Friday, December 11, 2009 3:16 PM To: math-fun Subject: Re: [math-fun] question ----- Original Message ----- From: "Cordwell, William R" <wrcordw@sandia.gov> To: "'math-fun'" <math-fun@mailman.xmission.com> Sent: Friday, December 11, 2009 4:31 PM Subject: Re: [math-fun] question
Can phi(n) divide n - 1, if n is not a prime?
If n contains a power of a prime, p (the power being bigger than or equal to 2), then there's a contradiction, because phi(n) is divisible by p, but n-1 is not divisible by p.
Also, n is not even, because n-1 would be odd, which cannot be divisible by phi(n) [unless n = 2 exactly].
Claim: if r and s are odd, then (r-1)(s-1) > 1/2 * rs. Consider (r-1)(s-1) = rs - (r+s) + 1 > rs/2 iff rs/2 + 1 > (r+s) Let r < s, then r+s < 2s. But if r >= 5, then rs/2 > 2s. So it is enough to show it for r = 3 (and r<s). Then we must show that 2(s-1) > 3/2 s, where s >= 5, but this is clear.
Now we can build up (p1-1)(p2-1)(p3-1) > (p1*p2/2)*(p3-1) > p1*p2*p3/2, etc.
So, for phi(n) to divide n - 1, since n does not contain a non-trivial power of a prime, n is of the form p1*p2*...*pn, where all of the pi's are odd. But then phi(n) > 1/2 * n, so it cannot divide n - 1.
Not true. Take n = 105 = 3*5*7. Then phi(n) = 48 < 1/2 * n.
So for your original question, yes, I think so.
-----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of David Wilson Sent: Friday, December 11, 2009 1:46 PM To: math-fun Subject: [math-fun] question
x == 1 (mod phi(x)) ==> x prime? (x >= 2)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-------------------------------------------------------------------------------- No virus found in this incoming message. Checked by AVG - www.avg.com Version: 8.5.426 / Virus Database: 270.14.103/2558 - Release Date: 12/11/09 10:06:00 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Of course, (p1*p2/2)*(p3-1) < p1*p2*p3/2, not greater than. -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of David Wilson Sent: Friday, December 11, 2009 3:16 PM To: math-fun Subject: Re: [math-fun] question ----- Original Message ----- From: "Cordwell, William R" <wrcordw@sandia.gov> To: "'math-fun'" <math-fun@mailman.xmission.com> Sent: Friday, December 11, 2009 4:31 PM Subject: Re: [math-fun] question
Can phi(n) divide n - 1, if n is not a prime?
If n contains a power of a prime, p (the power being bigger than or equal to 2), then there's a contradiction, because phi(n) is divisible by p, but n-1 is not divisible by p.
Also, n is not even, because n-1 would be odd, which cannot be divisible by phi(n) [unless n = 2 exactly].
Claim: if r and s are odd, then (r-1)(s-1) > 1/2 * rs. Consider (r-1)(s-1) = rs - (r+s) + 1 > rs/2 iff rs/2 + 1 > (r+s) Let r < s, then r+s < 2s. But if r >= 5, then rs/2 > 2s. So it is enough to show it for r = 3 (and r<s). Then we must show that 2(s-1) > 3/2 s, where s >= 5, but this is clear.
Now we can build up (p1-1)(p2-1)(p3-1) > (p1*p2/2)*(p3-1) > p1*p2*p3/2, etc.
So, for phi(n) to divide n - 1, since n does not contain a non-trivial power of a prime, n is of the form p1*p2*...*pn, where all of the pi's are odd. But then phi(n) > 1/2 * n, so it cannot divide n - 1.
Not true. Take n = 105 = 3*5*7. Then phi(n) = 48 < 1/2 * n.
So for your original question, yes, I think so.
-----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of David Wilson Sent: Friday, December 11, 2009 1:46 PM To: math-fun Subject: [math-fun] question
x == 1 (mod phi(x)) ==> x prime? (x >= 2)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-------------------------------------------------------------------------------- No virus found in this incoming message. Checked by AVG - www.avg.com Version: 8.5.426 / Virus Database: 270.14.103/2558 - Release Date: 12/11/09 10:06:00 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
David Wilson wrote:
x == 1 (mod phi(x)) ==> x prime? (x >= 2)
This was conjectured by D.H. Lehmer in 1932 and remains open. There are many references at B37 in Guy's _Unsolved Problems in Number Theory_. Lehmer noted in his original article that the problem was similar to that of odd perfect numbers, and since then the published results have had the same flavor: a counterexample must have a certain form, must be large, must have many prime divisors, etc. -- Fred W. Helenius fredh@ix.netcom.com
participants (3)
-
Cordwell, William R -
David Wilson -
Fred W. Helenius