Browse Groups

• ## Re: Lehmer's Totient Problem, Finally

(8)
• NextPrevious
• i forgot to add the word possible divisors.
Message 1 of 8 , May 26
View Source
i forgot to add the word 'possible' divisors.

--- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@...> wrote:
>
> the third time's a charm... I had to re-write the proof.
> now, it truly IS a classic. it's done, done, done!
> ...
> D. H. Lehmer's (1932) Totient Conjecture Stated: phi(n)
> divides (n -1) iff 'n' is prime.
> (proof, backward)
> if 'n' is prime, then phi(n) = (n -1) by definition, and
> phi(n) | (n -1), exactly as desired.
> (proof, forward)
> let phi(n) divide (n -1), such that k*phi(n)= (n -1), and
> assume 'n' is composite, n= b^j*C where gcd(b^j, C)= 1 and
> k <> 1. so, k*phi(b^j*C) = b^j*C -1, k*phi(b^j)*phi(C)= b^j
> *C -1, (k*b^j -k*b^(j-1))*phi(C)= b^j*C -1, or... phi(C)=
> [b^j*C -1] / [k*b^j - k*b^(j-1)] implies that k= b^(j-1)= 1.
> hence, phi(C) = (bC -1) / (b -1), b= C, and phi(C)= C +1.
> but, 'C' cannot have more co-prime divisors than it has a
> total number of /*possible*/ divisors. thus, 'n' must be
> prime.enjoy!
> ...
> *QED
> 05/26/2013
> ...
>
> --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@> wrote:
> >
> > ...
> > D. H. Lehmer's (1932) Totient Conjecture Stated:
> > phi(n) divides (n -1) iff 'n' is prime.
> > (proof, backward)
> > if 'n' is prime, then phi(n) = (n -1) by definition, and
> > phi(n) | (n -1), exactly as desired.
> > (proof, forward)
> > let phi(n) divide (n -1), or k*phi(n)= (n -1), and assume
> > 'n' is composite, or n= b^j*C where gcd(b^j, C)= 1 and k <> 1.
> > so, k*phi(b^j*C) implies k*b^j*C -k*b^(j-1)*C -1= b^j*C -1 and
> > adding one to... and dividing by b^(j-1) on... both sides, and
> > rearranging terms, we have... k= bC / [bC -1]. therefore, k= 1,
> > and phi(b^j*C) = b^j*C -1, and b^j*C -b^(j-1)*C = b^j*C -1 im-
> > plies b^(j-1)*C = 1, or b= C= 1, and 'n' isn't composite. thus,
> > 'n' must be prime. enjoy!
> > ...
> > *QED
> > 05/25/2013
> > ...
> > thanks, Jose B.; it's done! rewards, Bill
> >
> > --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@> wrote:
> > >
> > > here's what the missing portion would be similar to... let
> > > k <> 1, n= b^j*C is composite, and k*phi(b^j*C)= b^j*C -1
> > > where gcd(b, C)= 1. then we'd find that phi(C)= [b^j*C -1]
> > > / [k*b^(j-1)*(b- 1) -1]... forcing us to realize that k= 1
> > > and phi((b-1)/b) = phi(C) which is still a contradiction!
> > > we don't have to doubt the eventual answer.(5 more minutes)
> > > www.oddperfectnumbers.com
> > >
> > > --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@> wrote:
> > > >
> > > > I've presented to you the basics of how the proof would
> > > > take place. If you'd like to work through a few details
> > > > to improve upon my idea, then do so. If you aren't part
> > > > of the solution, then you're part of the problem...
> > > > rewards, Bill
> > > >
> > > > --- In primenumbers@yahoogroups.com, Jose Ramón Brox <ambroxius@> wrote:
> > > > >
> > > > > Note that phi(bC)=phi(b)phi(C) if and only if gcd(b,C)=1, but it could be
> > > > > that C=bC'.
> > > > >
> > > > > Regards,
> > > > > Jose Brox
> > > > >
> > > > >
> > > > > 2013/5/24 leavemsg1 <leavemsg1@>
> > > > >
> > > > > > **
> > > > > >
> > > > > >
> > > > > > a copy of this proof can be found at www.oddperfectnumbers.com
> > > > > > ...
> > > > > > D. H. Lehmer's (1932) Totient Conjecture Stated:
> > > > > > phi(n) divides (n -1) iff 'n' is prime.
> > > > > > (proof, backward)
> > > > > > if 'n' is prime, then phi(n) = (n -1) by definition, and phi(n)
> > > > > > divides (n -1), exactly.
> > > > > > (proof, forward)
> > > > > > let phi(n) divide (n -1), or k*phi(n) = (n -1), and 'n' isn't prime;
> > > > > > let n= bC where 'b' is one prime factor of 'n', and 'C' is one or more
> > > > > > other factors, combined, and k = 1. assume that k <> 1; so, k*phi(bC)
> > > > > > = bC -1; k*(b -1)*phi(C) = bC -1 such that phi(C) is equal to [bC -1]
> > > > > > / [b*k -k]; it has to be true that k= C= 1 in order for phi(C) to not
> > > > > > be fractional while phi(1) = (b -1) / (b -1) = 1 is verified. hence,
> > > > > > 1*phi(bC) = bC -1, and phi(b)*phi(C) = (bC -1), and phi(C) = [bC -1]
> > > > > > / [b -1] implies that C= b as the only solution. phi(C) = [b^2 -1] /
> > > > > > [b -1]; therefore, it's not possible to have phi(C)= C +1, (OR) there
> > > > > > cannot be more co-prime divisors of C than there are the total number
> > > > > > of possible divisors! thus, by contradiction, 'n' must be prime.
> > > > > > ...
> > > > > > it took me 20 minutes to solve Lehmer's Conjecture using a sharpie
> > > > > > marker on the back of a receipt for car repairs. at first glance, it
> > > > > > looks as though the problem needs to be solved using Fermat's little
> > > > > > theorem; that is DEFINITELY NOT the case. enjoy!
> > > > > > ...
> > > > > > *QED
> > > > > > 05/21/2013
> > > > > > ...
> > > > > > Bill Bouris
> > > > > > www.oddperfectnumbers.com
> > > > > >
> > > > > >
> > > > > >
> > > > >
> > > > >
> > > > >
> > > > > --
> > > > > La verdad (blog de raciocinio político e información
> > > > > social)<http://josebrox.blogspot.com/>
> > > > >
> > > > >
> > > > > [Non-text portions of this message have been removed]
> > > > >
> > > >
> > >
> >
>
• The readability is considerably improved apart from some Phis which have sneaked in. ... You say ... a step which I cannot follow. it is also evident for the
Message 1 of 8 , May 26
View Source
The readability is considerably improved apart from some Phis which have sneaked in.

--- In primenumbers@yahoogroups.com, "John" <mistermac39@...> wrote:
>
> For the sake of readability, I have set out the "backwards" part of the proof.

You say

> Ø implies that k= b^(j-1)= 1.

a step which I cannot follow. it is also evident for the preceding part of the proof that your k cannot take the value zero, otherwise we have some illegal division. And how, k could take any negative value, I cannot see. Now, k can take the value 1 only in the case of n being prime. Otherwise, the very meaning of Euler's Totients is debauched.

So, having by reasoning which eludes me, having shown that k can only have the value 1, which if true, of itself is sufficient to show that n cannot be composite without needing further comment.

Further, not only do you conclude that k = 1, you also conclude that b = C, and somehow, j completely fades from view, unless you are saying that j is also equal to 1, a conclusion that Lehmer himself proved by showing that n must be square free.

Now, if b = C, n is not square free. How you reasoned that b = C from the preceding part of the proof also eludes me. But, if your reasoning is correct, you have indeed come to the same conclusion as Lehmer. But, you have gone even one better, you have also proven that phi(b) = b + 1, which indeed is a contradiction.

So, the only thing missing is my failure to see that the conclusion that

> Ø implies that k= b^(j-1)= 1

part of the proof.

Any requirement that it is not necessary, as some say, to dismiss the possibility that n may be a Carmichael Number, (which would imply that C needs to be a composite number)is thus rendered spurious as far as I can see, as essentially you are using "reductio ad adsurdum" as your method of proof.

Thus ends my exercise in senile dementia aversion, which at the age of 73, I wish to try and avoid.

--- In primenumbers@yahoogroups.com, "John" <mistermac39@...> wrote:
>
> For the sake of readability, I have set out the "backwards" part of the proof.
>
> let phi(n) divide (n -1), such that k*phi(n)= (n -1), and
> Ø assume 'n' is composite,
> Ø n= b^j*C where gcd(b^j, C)= 1
> Ø and
> Ø k <> 1.
> Ø
> Ø so, k*phi(b^j*C) = b^j*C -1,
> Ø k*phi(b^j)*phi(C)= b^j*C -1,
> Ø (k*b^j -k*b^(j-1))*phi(C)= b^j*C -1,
> Ø or... phi(C)=[b^j*C -1] / [k*b^j - k*b^(j-1)]
> Ø
> Ø implies that k= b^(j-1)= 1.
> Ø
> Ø > hence, phi(C) = (bC -1) / (b -1),
> Ø b= C,
> Ø and phi(C)= C +1.
> Ø
> but, 'C' cannot have more co-prime divisors than it has a
> > > total number of /*possible*/ divisors. thus, 'n' must be
> > > prime.enjoy!
>
>
> --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@> wrote:
> >
> > i forgot to add the word 'possible' divisors.
> >
> > --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@> wrote:
> > >
> > > the third time's a charm... I had to re-write the proof.
> > > now, it truly IS a classic. it's done, done, done!
> > > ...
> > > D. H. Lehmer's (1932) Totient Conjecture Stated: phi(n)
> > > divides (n -1) iff 'n' is prime.
> > > (proof, backward)
> > > if 'n' is prime, then phi(n) = (n -1) by definition, and
> > > phi(n) | (n -1), exactly as desired.
> > > (proof, forward)
> > > let phi(n) divide (n -1), such that k*phi(n)= (n -1), and
> > > assume 'n' is composite, n= b^j*C where gcd(b^j, C)= 1 and
> > > k <> 1. so, k*phi(b^j*C) = b^j*C -1, k*phi(b^j)*phi(C)= b^j
> > > *C -1, (k*b^j -k*b^(j-1))*phi(C)= b^j*C -1, or... phi(C)=
> > > [b^j*C -1] / [k*b^j - k*b^(j-1)] implies that k= b^(j-1)= 1.
> > > hence, phi(C) = (bC -1) / (b -1), b= C, and phi(C)= C +1.
> > > but, 'C' cannot have more co-prime divisors than it has a
> > > total number of /*possible*/ divisors. thus, 'n' must be
> > > prime.enjoy!
> > > ...
> > > *QED
> > > 05/26/2013
> > > ...
> > >
> > > --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@> wrote:
> > > >
> > > > ...
> > > > D. H. Lehmer's (1932) Totient Conjecture Stated:
> > > > phi(n) divides (n -1) iff 'n' is prime.
> > > > (proof, backward)
> > > > if 'n' is prime, then phi(n) = (n -1) by definition, and
> > > > phi(n) | (n -1), exactly as desired.
> > > > (proof, forward)
> > > > let phi(n) divide (n -1), or k*phi(n)= (n -1), and assume
> > > > 'n' is composite, or n= b^j*C where gcd(b^j, C)= 1 and k <> 1.
> > > > so, k*phi(b^j*C) implies k*b^j*C -k*b^(j-1)*C -1= b^j*C -1 and
> > > > adding one to... and dividing by b^(j-1) on... both sides, and
> > > > rearranging terms, we have... k= bC / [bC -1]. therefore, k= 1,
> > > > and phi(b^j*C) = b^j*C -1, and b^j*C -b^(j-1)*C = b^j*C -1 im-
> > > > plies b^(j-1)*C = 1, or b= C= 1, and 'n' isn't composite. thus,
> > > > 'n' must be prime. enjoy!
> > > > ...
> > > > *QED
> > > > 05/25/2013
> > > > ...
> > > > thanks, Jose B.; it's done! rewards, Bill
> > > >
> > > > --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@> wrote:
> > > > >
> > > > > here's what the missing portion would be similar to... let
> > > > > k <> 1, n= b^j*C is composite, and k*phi(b^j*C)= b^j*C -1
> > > > > where gcd(b, C)= 1. then we'd find that phi(C)= [b^j*C -1]
> > > > > / [k*b^(j-1)*(b- 1) -1]... forcing us to realize that k= 1
> > > > > and phi((b-1)/b) = phi(C) which is still a contradiction!
> > > > > we don't have to doubt the eventual answer.(5 more minutes)
> > > > > www.oddperfectnumbers.com
> > > > >
> > > > > --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@> wrote:
> > > > > >
> > > > > > I've presented to you the basics of how the proof would
> > > > > > take place. If you'd like to work through a few details
> > > > > > to improve upon my idea, then do so. If you aren't part
> > > > > > of the solution, then you're part of the problem...
> > > > > > rewards, Bill
> > > > > >
> > > > > > --- In primenumbers@yahoogroups.com, Jose Ramón Brox <ambroxius@> wrote:
> > > > > > >
> > > > > > > Note that phi(bC)=phi(b)phi(C) if and only if gcd(b,C)=1, but it could be
> > > > > > > that C=bC'.
> > > > > > >
> > > > > > > Regards,
> > > > > > > Jose Brox
> > > > > > >
> > > > > > >
> > > > > > > 2013/5/24 leavemsg1 <leavemsg1@>
> > > > > > >
> > > > > > > > **
> > > > > > > >
> > > > > > > >
> > > > > > > > a copy of this proof can be found at www.oddperfectnumbers.com
> > > > > > > > ...
> > > > > > > > D. H. Lehmer's (1932) Totient Conjecture Stated:
> > > > > > > > phi(n) divides (n -1) iff 'n' is prime.
> > > > > > > > (proof, backward)
> > > > > > > > if 'n' is prime, then phi(n) = (n -1) by definition, and phi(n)
> > > > > > > > divides (n -1), exactly.
> > > > > > > > (proof, forward)
> > > > > > > > let phi(n) divide (n -1), or k*phi(n) = (n -1), and 'n' isn't prime;
> > > > > > > > let n= bC where 'b' is one prime factor of 'n', and 'C' is one or more
> > > > > > > > other factors, combined, and k = 1. assume that k <> 1; so, k*phi(bC)
> > > > > > > > = bC -1; k*(b -1)*phi(C) = bC -1 such that phi(C) is equal to [bC -1]
> > > > > > > > / [b*k -k]; it has to be true that k= C= 1 in order for phi(C) to not
> > > > > > > > be fractional while phi(1) = (b -1) / (b -1) = 1 is verified. hence,
> > > > > > > > 1*phi(bC) = bC -1, and phi(b)*phi(C) = (bC -1), and phi(C) = [bC -1]
> > > > > > > > / [b -1] implies that C= b as the only solution. phi(C) = [b^2 -1] /
> > > > > > > > [b -1]; therefore, it's not possible to have phi(C)= C +1, (OR) there
> > > > > > > > cannot be more co-prime divisors of C than there are the total number
> > > > > > > > of possible divisors! thus, by contradiction, 'n' must be prime.
> > > > > > > > ...
> > > > > > > > it took me 20 minutes to solve Lehmer's Conjecture using a sharpie
> > > > > > > > marker on the back of a receipt for car repairs. at first glance, it
> > > > > > > > looks as though the problem needs to be solved using Fermat's little
> > > > > > > > theorem; that is DEFINITELY NOT the case. enjoy!
> > > > > > > > ...
> > > > > > > > *QED
> > > > > > > > 05/21/2013
> > > > > > > > ...
> > > > > > > > Bill Bouris
> > > > > > > > www.oddperfectnumbers.com
> > > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > > >
> > > > > > >
> > > > > > >
> > > > > > > --
> > > > > > > La verdad (blog de raciocinio político e información
> > > > > > > social)<http://josebrox.blogspot.com/>
> > > > > > >
> > > > > > >
> > > > > > > [Non-text portions of this message have been removed]
> > > > > > >
> > > > > >
> > > > >
> > > >
> > >
> >
>
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.