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

Re: If q divides a^p +b^p then p divides q-1

Expand Messages
  • hillcino368
    Mike Oakes proved ... are ... Can we also prove the case for N=a^p+b^p? ... of m, ... Cino
    Message 1 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 2 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 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
          >
          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.