[seqfan] Re: Proof

[Andrew Weimholt]

Meant to say...

for some n,  gcd ( n, (n-1)! ) = n

seems I can't even get the correction right the first time. :-P

Andrew

On 12/1/09, Andrew Weimholt <andrew.weimholt at gmail.com> wrote:
> Spotted an error!
>
>  for some n, gcd( n, (n-1)! ) = (n-1)!
>
>  This invalidates the (attempted) proof.
>  Got caught doing my thinking on the keyboard instead of on paper again :-)
>
>
>  Andrew
>
>
>  On 11/30/09, Andrew Weimholt <andrew.weimholt at gmail.com> wrote:
>  > Franklin T. Adams-Watters recently submitted A167234, and poses a
>  >  question in the comments:
>  >
>  >  "What can we say about the asymptotic behavior of this sequence? Does
>  >  it contain every integer > 2 infinitely often?"
>  >
>  >  The answer is yes, and here is the proof...
>  >
>  >  By Dirichlet's Theorem, there are an infinite number of primes of the
>  >  form dk + b, for any positive coprimes d & b
>  >  Furthermore, Dirichlet showed that the primes are evenly distributed
>  >  over the phi(d) arithmetic progressions with difference d coprime to
>  >  the first term.
>  >  Thus the for a given d & b, the primes of the form dk + b account for
>  >  1 / phi(d) of the primes.
>  >
>  >  If we let d = (n-1)!, for n > 2
>  >  and b = 1,
>  >
>  >  it follows that there are an infinite number of primes of the form
>  >  k*(n-1)! + 1,
>  >  and they account for 1 / phi( (n-1)! ) of the primes.
>  >
>  >  In order to prove that the answer to Franklin's question is "yes", we will need
>  >  to show that the number of primes of the form k*(n-1)! + 1 is still
>  >  infinite when
>  >  we add the restriction that n does not divide k*(n-1)!
>  >
>  >  For each k, where n | ( k*(n-1)! )
>  >
>  >  there exists some t > 0, such that k = t * n / gcd(n, (n-1)! )
>  >
>  >  Substituting into k(n-1)! + 1, we get
>  >
>  >  t * n! / gcd ( n, (n-1)! ) + 1
>  >
>  >  which is also an arithmetic progression for a given n, and t = 1, 2, 3, ...
>  >
>  >  If there are not an infinite number of primes of the form k(n-1)! + 1,
>  >  where n does not divide k(n-1)!,
>  >
>  >  then all of the primes of the form, k(n-1)! + 1 are also of the form t
>  >  * n! / gcd( n, (n-1)! )
>  >
>  >  implying that
>  >
>  >  phi( (n-1)! ) = phi( n! / gcd( n, (n-1)! ) )
>  >
>  >  which we will now show is false
>  >
>  >  case 1: n is composite:
>  >
>  >  then n / gcd( n, (n-1)! ) is at least 2, meaning, n! / gcd( n, (n-1)!
>  >  ) is at least 2(n-1)!
>  >
>  >  For x>1, there is always a prime in the interval (x, 2x).
>  >
>  >  Therefore we have coprimes of n! / gcd( n, (n-1)! ) less than n! /
>  >  gcd( n, (n-1)! ) and greater than (n-1)!
>  >
>  >  Also, since n is not prime, there are no prime factors of n, not
>  >  already in (n-1)!,
>  >  so all numbers less than (n-1)! which are coprime to (n-1)! are also
>  >  coprime to n! / gcd( n, (n-1)! )
>  >
>  >  Therefore, phi( n! / gcd( n, (n-1) ) ) > phi( (n-1)! )
>  >
>  >  case 2: n is prime:
>  >
>  >  then phi( n! / gcd( n, (n-1)! ) ) = phi( n! ) > phi( (n-1)! )
>  >
>  >  (Cf. A048855 : a(n) = phi ( n! ). Formula: a(n) = a(n-1)*n for
>  >  composite n, and a(n) = a(n-1)*(n-1) for prime n.)
>  >
>  >  Therefore, there are an infinite number of primes of the form k(n-1)!
>  >  + 1 which are not congruent to 1 mod n.
>  >
>  >  These primes are congruent to 1 mod x for all x in {1,2,...,n-1},
>  >  therefore, for these primes, n is the smallest modulus,
>  >  for which their two divisors are not congruent.
>  >
>  >  Therefore, all numbers > 2 appear infinitely often in A167234.
>  >
>  >
>  >  Andrew
>  >
>