## Re: [PrimeNumbers] p, q prime. Prove if q divides x^p - (x-1)^p -1, then ...

Expand Messages
• In a message dated 16/12/03 17:08:42 GMT Standard Time, ... Your Theorem 1 is a special case of a more general theorem, which will now be proved. Theorem: Let
Message 1 of 4 , Dec 16, 2003
In a message dated 16/12/03 17:08:42 GMT Standard Time,
hillcino368@... writes:

> I have been trying to prove and searching (Eg., the entire Caldwell Suite
> et
> al) for a proof of the
> following theorem I conjured by inspection.
>
> Theorem I
> Let p and q be primes. if q divides N=x^p - (x-1)^p for some integer x,
> then p divides q-1
> and q = 2kp+1 for some integer k. If N is prime then N-1 = q-1 and the
> theorem still holds.
>

Your Theorem 1 is a special case of a more general theorem, which will now be
proved.

Theorem:
Let p and q be odd primes, and q divide N=a^p-b^p, where a and b are
arbitrary positive integers except for the condition
a <> b mod q.
Then q = 2*k*p + 1, for some integer k > 0.

Proof:
As q | N, a^p = b^p mod q.
.
Let m be the _least_ power such that a^m = b^m mod q.
Then, since a^p = b^p mod q, p must be a multiple of m.

[It is easy to show that if p is not a multiple of m, then we get a
contradiction to m being the _smallest_ power,
as r = p mod m also satisfies a^r = b^r mod q and r < m.]

m <> 1, as a-b <> 0 mod q by assumption.

Thus, since p is prime and a multiple of m, p = m.

By Fermat's Little Theorem:
a^(q-1) = b^(q-1) mod q.

So, by the same reasoning as outlined above, (q-1) is a multiple of m,
i.e. (q-1) is a multiple of p.

As q and p are odd, (q-1) is even, so:
q = 2*k*p + 1.

Q.E.D.

-Mike Oakes

[Non-text portions of this message have been removed]
• Mike Oakes proved ... are ... Can we also prove the case for N=a^p+b^p? ... of m, ... Cino
Message 2 of 4 , Mar 5, 2004
Mike Oakes proved
> Theorem:
> Let p and q be odd primes, and q divide N=a^p-b^p, where a and b
are
> arbitrary positive integers except for the condition
> a <> b mod q.
> Then q = 2*k*p + 1, for some integer k > 0.

Can we also prove the case for N=a^p+b^p?

>
> Proof:
> As q | N, a^p = b^p mod q.
> .
> Let m be the _least_ power such that a^m = b^m mod q.
> Then, since a^p = b^p mod q, p must be a multiple of m.
>
> [It is easy to show that if p is not a multiple of m, then we get a
> contradiction to m being the _smallest_ power,
> as r = p mod m also satisfies a^r = b^r mod q and r < m.]
>
> m <> 1, as a-b <> 0 mod q by assumption.
>
> Thus, since p is prime and a multiple of m, p = m.
>
> By Fermat's Little Theorem:
> a^(q-1) = b^(q-1) mod q.
>
> So, by the same reasoning as outlined above, (q-1) is a multiple
of m,
> i.e. (q-1) is a multiple of p.
>
> As q and p are odd, (q-1) is even, so:
> q = 2*k*p + 1.
>
> Q.E.D.
>
> -Mike Oakes

Cino
• In a message dated 05/03/04 09:26:14 GMT Standard Time, ... Yes. Nowhere is the positivity of a or b used in the proof (so the Theorem should not have required
Message 3 of 4 , Mar 5, 2004
In a message dated 05/03/04 09:26:14 GMT Standard Time,
hillcino368@... writes:

> Mike Oakes proved
> > Theorem:
> > Let p and q be odd primes, and q divide N=a^p-b^p, where a and b
> are
> > arbitrary positive integers except for the condition
> > a <> b mod q.
> > Then q = 2*k*p + 1, for some integer k > 0.
>
> Can we also prove the case for N=a^p+b^p?
>

Yes.
Nowhere is the positivity of a or b used in the proof (so the Theorem should
not have required this, in fact).
Putting b => -b gives your case (since p is odd).

-Mike Oakes

[Non-text portions of this message have been removed]
• ... But of course! Thanks. I also noticed that if p is not prime then the prime factors of p divide q-1. This applies to even numbers also. Does the even case
Message 4 of 4 , Mar 5, 2004
>In a message dated 05/03/04 09:26:14 GMT Standard Time,
>hillcino368@... writes:
>
>
> > Mike Oakes proved
> > > Theorem:
> > > Let p and q be odd primes, and q divide N=a^p-b^p, where a and b
> > are
> > > arbitrary positive integers except for the condition
> > > a <> b mod q.
> > > Then q = 2*k*p + 1, for some integer k > 0.
> >
> > Can we also prove the case for N=a^p+b^p?
> >
>
>Yes.
>Nowhere is the positivity of a or b used in the proof (so the Theorem
>should
>not have required this, in fact).
>Putting b => -b gives your case (since p is odd).
>
>-Mike Oakes
>
But of course! Thanks.

I also noticed that if p is not prime then the prime factors of p divide
q-1. This applies to even numbers also. Does the even case follow from
a^(2p) - b^(2p) = (a^p-b^p)(a^p+b^p) =
q1*q2*q3*...?

Cino

_________________________________________________________________
Create a Job Alert on MSN Careers and enter for a chance to win \$1000!