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

FW: [PrimeNumbers] Factor patterns

Expand Messages
  • Insall
    Replied to djbroadhurst, but fergitted that replies in this group don t go to group. .... o}o:-:o{o ... From: Insall [mailto:montez@rollanet.org] Sent:
    Message 1 of 4 , Jul 2, 2002
      Replied to djbroadhurst, but fergitted that replies in this group don't go
      to group. .... o}o:-:o{o



      -----Original Message-----
      From: Insall [mailto:montez@...]
      Sent: Monday, July 01, 2002 6:11 AM
      To: djbroadhurst
      Subject: RE: [PrimeNumbers] Factor patterns


      Proposition: Let n be a positive integer such that for every pair a, b in
      Z_n with ab=-1, we have a+b=0. Then for every pair a,b in Z_n such that
      ab=-1, we have a^2=b^2=1.

      Proof:
      Let a, b in Z_n with ab=-1. Then

      a^2=a^2-1+1=a^2+ab+1=a(a+b)+1=a(0)+1=1.

      A similar argument works for b. (In fact, this observation is quite
      trivial, but all such things include a bit of fun. :-} )

      qed

      Example: If a, b are in z_12 and ab=-1, then {a,b} is either {1,11} or
      {5,7}. Since in Z_12, 1^2=1, 11^2=(-1)^2=1, 5^2=25=1 and 7^2=49=1, this is
      an example of the proposition.

      What more can be said about those positive integers n for which the set of
      pairs a, b in Z_n such that ab=-1 is a subset of the set of pairs of the
      form (a,b)=(a,-a)? (In particular, does this hold for all n?)

      Well, the answer is not immediate, as the following proposition suggests.

      Proposition: There exists a finite nontrivial ring R in which there are
      elements a, b such that ab=-1 and a+b=1. The ring R can be taken to be a
      field of any finite (prime) characteristic, and in this field, one can prove
      that if ab=-1 and a+b=1, then both a and b are zeros of the polynomial
      x^2-x-1. Moreover, if p is the characterisic of this field R, then R need
      not have more than p^2 elements.

      Proof:
      This is a simple exercise in finite field theory. I shall do some and
      leave the rest for the restless. Let p be any prime number whatsoever, and
      let R be the splitting field for the polynomial x^2-x-1 over Z_p. Let a and
      b be the roots (counting multiplicities) in R of the equation x^2-x-1=0.
      Then

      x^2-x-1=(x-a)(x-b)=x^2-(a+b)x+ab.

      It follows that ab=-1 and a+b=1. Note that R is an at most degree two
      extension field of Z_p, so R has at most p^2 elements. It is easy to show
      that in any ring, if a and b are such that ab=-1 and a+b=1, then a^2-a-1=0
      and similarly b^2-b-1=0.

      qed

      But this shows that one must work a bit harder to determine the rings in
      which ab=-1 implies a+b=0. (But it may not be very much harder. I am just
      thinking while I wile away some time here...)


      Well now, there is a root of the equation x^2-x-1=0 in Z_19. (I know, I
      know, it's a prime field, but I work slowly...) In particular, 5 works in
      Z_19. The other root in z_19 is 15, and we have 5(15)=5(-4)=-20=-1 in Z_19.
      Son o ma gun, she works out! In Z_19, Markus' theorem holds.

      Is there a composite n for which there are a, b in Z_n with ab=-1 but
      a+b<>0? I think so...

      Let n=55 and a=8 and b=48. Then ab=-1, and a+b=1. Hence the Markus result
      about n=12, when generalized ad nauseum, picks out some ``special'' positive
      integers. Let us call them ``Markus' positive integers''. Which primes are
      ``Markus' primes''?

      Proposition: Let p be a Markus' prime. Then the only elements a of Z_p for
      which there is an element b with both ab=-1 and a+b=0, are 1 and -1.

      Proof:
      This is because a^2=1.

      qed





      Matt



      -----Original Message-----
      From: djbroadhurst [mailto:d.broadhurst@...]
      Sent: Sunday, June 30, 2002 10:53 PM
      To: primenumbers@yahoogroups.com
      Subject: [PrimeNumbers] Factor patterns


      Markus observed:
      If a*b=-1 mod 12 then a+b=0 mod 12.
      Proof is easy: The only residue pairs
      for {a,b} mod 12 are {1,11} or {5,7}.
      It's true for both of these pairs,
      so we are done.
      David



      Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
      The Prime Pages : http://www.primepages.org



      Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
    • Markus Frind
      Here are the first few primes, note that 55 is made up of the first 2 primes in our series. The only composites that can be generated have to be divisible
      Message 2 of 4 , Jul 2, 2002
        Here are the first few primes, note that 55 is made up of the first 2
        primes in our series. The only composites that can be generated have to
        be divisible by primes generated previously in the series. 11*5 =
        55, the next smallest composite is 5*19 = 95 (43,53). The smallest 3
        prime composite possible is 5*11*19 .

        5 (3,3)
        11 (4,8)
        19 (5,15)
        29 (6,24)
        31 (13,19)
        41 (7,35)
        55 (8,48)

        Many of these numbers are simple to generate because all you need to do is
        subtract n from the closest square and then subtract one. Which is for the
        most part the same as saying x^2-x-1=0
        n^2-x-1=0 (49 -41-1) = 7


        >Well now, there is a root of the equation x^2-x-1=0 in Z_19. (I know, I
        >know, it's a prime field, but I work slowly...) In particular, 5 works in
        >Z_19. The other root in z_19 is 15, and we have 5(15)=5(-4)=-20=-1 in Z_19.
        >Son o ma gun, she works out! In Z_19, Markus' theorem holds.
        >
        >Is there a composite n for which there are a, b in Z_n with ab=-1 but
        >a+b<>0? I think so...
        >
        >Let n=55 and a=8 and b=48. Then ab=-1, and a+b=1. Hence the Markus result
        >about n=12, when generalized ad nauseum, picks out some ``special'' positive
        >integers. Let us call them ``Markus' positive integers''. Which primes are
        >``Markus' primes''?
        >
        >Proposition: Let p be a Markus' prime. Then the only elements a of Z_p for
        >which there is an element b with both ab=-1 and a+b=0, are 1 and -1.
        >
        >Proof:
        > This is because a^2=1.
        >
        >qed
        >
        >
        >
        >
        >
        >Matt
        >
        >
        >
        >-----Original Message-----
        >From: djbroadhurst [mailto:d.broadhurst@...]
        >Sent: Sunday, June 30, 2002 10:53 PM
        >To: primenumbers@yahoogroups.com
        >Subject: [PrimeNumbers] Factor patterns
        >
        >
        >Markus observed:
        >If a*b=-1 mod 12 then a+b=0 mod 12.
        >Proof is easy: The only residue pairs
        >for {a,b} mod 12 are {1,11} or {5,7}.
        >It's true for both of these pairs,
        >so we are done.
        >David
        >
        >
        >
        >Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
        >The Prime Pages : http://www.primepages.org
        >
        >
        >
        >Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
        >
        >
        >
        >
        >Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
        >The Prime Pages : http://www.primepages.org
        >
        >
        >
        >Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
      • Markus Frind
        I wanted to add one more thing, can anyone explain why the following pattern has emerged? 11 = 5+(3*2), 19 = 11 + (4*2), 29 = 19 + (5*2)... to fininity? 5
        Message 3 of 4 , Jul 2, 2002
          I wanted to add one more thing, can anyone explain why the following
          pattern has emerged? 11 = 5+(3*2), 19 = 11 + (4*2), 29 = 19 + (5*2)...
          to fininity?

          5 3, 3
          11 4, 8
          19 5, 15
          29 6, 24
          41 7
          55 8
          71 9
          89 10
          109 11
          131 12
          155 13
          181 14
          209 15
          239 16
          271 17
          305 18
          341 19
          379 20
          419 21
          461 22
          505 23
          551 24
          599 25
          649 26
          701 27
          755 28
          811 29
          869 30
        • Markus Frind
          To explain this pattern, you also have to explain why, 31 with A and B 13 and 19 divides elements 13 (155), and 19 (341) of the pattern, same with 59 with
          Message 4 of 4 , Jul 2, 2002
            To explain this pattern, you also have to explain why, 31 with A and B 13
            and 19 divides elements 13 (155), and 19 (341) of the pattern, same with
            59 with a,b 26 and 34 divide elements 26 and 24 of the main pattern
            below... All primes/composites that have a*b=-1 and a+b=1 pattern follow
            this pattern.

            At 07:37 PM 7/2/2002 -0700, Markus Frind wrote:
            >I wanted to add one more thing, can anyone explain why the following
            >pattern has emerged? 11 = 5+(3*2), 19 = 11 + (4*2), 29 = 19 + (5*2)...
            >to fininity?
            >
            >5 3, 3
            >11 4, 8
            >19 5, 15
            >29 6, 24
            >41 7
            >55 8
            >71 9
            >89 10
            >109 11
            >131 12
            >155 13
            >181 14
            >209 15
            >239 16
            >271 17
            >305 18
            >341 19
            >379 20
            >419 21
            >461 22
            >505 23
            >551 24
            >599 25
            >649 26
            >701 27
            >755 28
            >811 29
            >869 30
            >
            >
            >Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
            >The Prime Pages : http://www.primepages.org
            >
            >
            >
            >Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
          Your message has been successfully submitted and would be delivered to recipients shortly.