Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • mikeoakes2@aol.com
    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
    • 0 Attachment
      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]
    • hillcino368
      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
      • 0 Attachment
        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
      • mikeoakes2@aol.com
        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
        • 0 Attachment
          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]
        • cino hilliard
          ... 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
          • 0 Attachment
            >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!
            http://msn.careerbuilder.com/promo/kaday.htm?siteid=CBMSN_1K&sc_extcmp=JS_JASweep_MSNHotm2
          Your message has been successfully submitted and would be delivered to recipients shortly.