Re: -- f(k) = k^(n-1) (mod n)

On Mon, 19 Jan 2009 12:33:05 -0500, quasi <quasi@xxxxxxxx> wrote:

On Mon, 19 Jan 2009 08:19:10 -0800 (PST), cbrown@xxxxxxxxxxxxxxxxx
wrote:

On Jan 19, 7:56 am, no comment <adler.m...@xxxxxxxxx> wrote:
On Jan 19, 7:04 am, quasi <qu...@xxxxxxxx> wrote:



On Mon, 19 Jan 2009 00:01:57 -0800 (PST), cbr...@xxxxxxxxxxxxxxxxx
wrote:

On Jan 18, 10:34 pm, no comment <adler.m...@xxxxxxxxx> wrote:
On Jan 18, 8:27 pm, quasi <qu...@xxxxxxxx> wrote:
On Sat, 17 Jan 2009 20:56:10 -0800 (PST), cbr...@xxxxxxxxxxxxxxxxx
wrote:
On Jan 15, 7:45 pm, quasi <qu...@xxxxxxxx> wrote:
On Thu, 15 Jan 2009 18:49:22 -0500, quasi <qu...@xxxxxxxx> wrote:
On Wed, 14 Jan 2009 23:21:53 -0500, quasi <qu...@xxxxxxxx> wrote:

Let n in N, n > 1.

For k in Z, define f(k) = k^(n-1) (mod n).

Problem (4):

Prove or disprove: If n is composite, then gcd(s,n) > 1, where

        s = f(1) + f(2) + ... + f(n-1)

Problem (4) was disproved using the Carmichael Number n = 561.

So maybe the problem can be salvaged by just barring Carmichael
Numbers. Let's try it ...

Problem (4) [revised]:

Prove or disprove: If n is composite, but not a Carmichael Number,
then gcd(s,n) > 1, where

  s = f(1) + f(2) + ... + f(n-1)

Since the case where n is even has an easy proof, we need only
consider odd composite n.

Moreover, for the case of odd composite n, I think a strengthened
version is warranted, recasting it as an iff criterion for Carmichael
Numbers, as follows ...

Conjecture:

An odd composite number n is such that the sum

   1^(n-1) + 2^(n-1) + ... + (n-1)^(n-1)

is relatively prime to n iff n is a Carmichael Number.

quasi

Let's write g(n) = sum{i=1 to (n-1)} i^(n-1).

Given the lemmas [*]:

Lemma 1: If p prime and not (p-1) | m, then sum{i=1 to p} (i^m) = 0
mod p.

As in your comment below, the proof of lemma 1 works out easily if
gcd(p-1, m)=1, but for the general situation where all you have is
that p-1 does not divide m, I don't see how to prove it. Nevertheless,
testing with Maple suggests that lemma 1 does hold.

Lemma 2: If p prime and (p-1) | m, then sum{i=1 to p} (i^m) = -1 mod
p.

On the other hand, lemma 2 is immediate, since for 1 <= i < p-1,
Fermat's Little Theorem gives i^(p-1) = 1 (mod p), which then implies
i^m = 1 (mod p), so the sum (mod p) equals p-1, which reduces to -1
(mod p).

then we can make a slighty stronger statement; gcd(n,g(n))=1 iff n is
prime or n is a Carmichael number.

It's easy that n is prime or Carmicheal -> g(n) = (n-1) which is
coprime to n;

Well, if n is prime, no problem.

But if n is a Carmichael number, I don't see why g(n) = n-1.

I haven't done any testing on this aspect, but my intuition is that
this is the weak link in my conjecture. In other words, it's
conceivable to me (at this point, with no immediately apparent proof
otherwise) that there might in fact be a Carmichael number n such that
g(n) has a common factor with n. If so, such an n would break my
conjecture.

so let us look at the other direction.

First, if p is a prime and p | n, then, since for all integers k, a^m
= (a + kp)^m mod p, and since p | n, n^(n-1) = 0 mod p, it follows
that

sum{i=1 to (n-1)} i^(n-1) = sum{i=1 to n} i^(n-1) mod p
                         = (n/p)*sum{j=1 to p} (j^(n-1)) mod p.

Given the lemmas, if not (p-1) | (n-1), then sum{i=1 to (n-1)} i^(n-1)
= (n/p)*0 mod p, and so p | g(n).

And if (p-1) | (n-1), then for some set of naturals {a_i},

f(n) = sum{i=1 to (n/p)} (a_i*p - 1)
    = p*(sum {i=1 to (n/p)} a_i) - n/p

Then, since p | p*(sum {i=1 to (n/p)} a_i), we have p | f(n) iff p |
(n/p) iff p^2 | n.

Therefore, given composite n, for each prime p with p | n, if (not
(p-1) | (n-1)) or (p^2 | n), then p | g(n); or taking the
contrapositive, if gcd(n,g(n))=1, then n is square-free and every
prime factor p of n has (p-1) | (n-1).

But as Bill Dubuque showed, that is equivalent to: if gcd(n,g(n))=1,
then n is a Carmicheal number, completing the proof.

Nice argument.

It looks correct (provided lemma 1 is established).

Some of the problems with your argument that I had earlier seem to be
resolved. The only issues I have now are the lack of proof for lemma
1, and my earlier doubt concerning the immediacy of the "easy
direction" of the iff statement, for the case when n is a Carmichael
number.

Cheers - Chas

[*] I seem to recall that these are provable, but I can't quite see /
how/.

I know that the multiplicative group of Z/pZ is cyclic, so for any
generator x on that group, the sum in question can be expressed as

sum{i=1 to n-1} (x^(m*i))

Now, if gcd(p-1, m) = 1 then x :-> x^m is a bijection so in that case
p | the sum would follow. But I can't see how to proceed from there.

quasi

Hello,

It is not true that if n is a Carmichael number, then what you call g
(n) is congruent to -1 modulo n.  This already fails at n = 561, and
at n = 1105.  However, it is still perfectly possible that g(n) is
relatively prime to n for Carmichael numbers.

I (not quasi) was the one who claimed that; and you are correct: it is
rubbish.

However you are still going strong on your attempt to prove the
forward direction of my conjecture, in the a sense that, you've shown
that it will suffice to prove lemma 1.

I'll restate it here, slightly reworded ...

Prove or disprove:

If p prime, and m in N with 0 < m < p, then

   sum {i=1 to p} (i^m)= 0 (mod p).

quasi

Hello,

Maybe I should not have mentioned the example with p = 3, since it
happens to be the only example.

More precisely, let p be an odd prime, and let

f(n) = 1^n + 2^n + 3^n + ... + (p-1)^n.

Then f(n) is congruent to 0 modulo p unless p - 1 divides n.

A couple of proofs are given in the book "The Theory of Numbers" by
John Coury and me.  (In case you can find a copy, this is solved
problem 6-66, page 184).

The most mechanical proof is by using a primitive root.  Suppose that
p - 1 does not divide n, and let a be an integer not divisible by p,
to be chosen later.

Then a, 2a, 3a, up to (p-1)a are congruent, in some order, to 1, 2,
and so on up to p-1.

So a^n, (2a)^n, and so on are congruent, in some order, to 1^n, 2^n,
and so on.

Add up.  We get that (a^n)f(n) is congruent to f(n), and therefore
(a^n -1)f(n) is congruent to 0.

Now let a be a primitive root of p.  It is a standard fact that if p-1
does not divide n, then a^n is not congruent to 1.  So from (a^n - 1)f
(n) congruent to 0 we can conclude that f(n) is congruent to 0.

Nice proof.

So now we have that if gcd(n, g(n))=1, then n is prime or n is
Carmichael.

Yes.

Next it remains to show: if n is Carmichael, is gcd(n,g(n))=1?

I wouldn't bet much on it.

My intuition on this is now changed.

My gut feeling is that if n is a Carmichael number, then g(n) mod n is
essentially random.

Following that idea, the probability (informal probability) that g(n)
is relatively prime to n is approximately w(n)/n, where w(n) is the
number of distinct prime factors of n. Note -- I left out the
inclusion-exclusion corrections, since they are of a lower order of
magnitude (and in any case, the argument is only heuristic).

So the (informal probability) that, for all Carmichael numbers n, g(n)
is relatively prime to n, is approximately equal to the infinite
product

product {n is Carmichael} (1 - w(n)/n)

Clearly, the "probability", as given above, is less than 1, hence
there is at least some positive probability that for some Carmichael
number n, g(n) is not relatively prime to n. Is the probability more
or less than 1/2 (that determines which way I would bet, with no
evidence to the contrary). Of course, if the above product converges
to 0, then it's almost certain that a counterexample exists.

Well, I don't know if the heuristics I described above are valid, but
if they are, then all it means (given cbrown's cool proof of the
nonexistence of a counterexample) is that some event which had a
positive probability of happening didn't actually happen. Well, as
they say -- you win some, you lose some. However, in one of the
alternate universes, such a counterexample failed to occur (by the law
of conservation of probability).

quasi
.

Relevant Pages

  • Re: -- f(k) = k^(n-1) (mod n)
    ... recasting it as an iff criterion for Carmichael ... that p-1 does not divide m, I don't see how to prove it. ... prime or n is a Carmichael number. ... Then fis congruent to 0 modulo p unless p - 1 divides n. ...
    (sci.math)
  • Re: -- f(k) = k^(n-1) (mod n)
    ... recasting it as an iff criterion for Carmichael ... prime or n is a Carmichael number. ... Then fis congruent to 0 modulo p unless p - 1 divides n. ... the probability that g ...
    (sci.math)
  • Re: -- f(k) = k^(n-1) (mod n)
    ... recasting it as an iff criterion for Carmichael ... that p-1 does not divide m, I don't see how to prove it. ... prime or n is a Carmichael number. ... Then fis congruent to 0 modulo p unless p - 1 divides n. ...
    (sci.math)
  • Re: -- f(k) = k^(n-1) (mod n)
    ... recasting it as an iff criterion for Carmichael ... that p-1 does not divide m, I don't see how to prove it. ... prime or n is a Carmichael number. ... Then fis congruent to 0 modulo p unless p - 1 divides n. ...
    (sci.math)
  • Re: -- f(k) = k^(n-1) (mod n)
    ... recasting it as an iff criterion for Carmichael ... prime or n is a Carmichael number. ... this is the weak link in my conjecture. ... A simple pairing argument shows that this is true if p is an odd ...
    (sci.math)