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

At least one relatively prime

Expand Messages
  • Mark
    I have no doubt that others are familiar with this, but I can t recall encountering it before. It s a very simple (I like simple!) observation: Given two or
    Message 1 of 5 , Oct 13, 2011
    • 0 Attachment
      I have no doubt that others are familiar with this, but I can't recall encountering it before. It's a very simple (I like simple!) observation:

      Given two or more consecutive numbers greater than 1, at least one of them will be relatively prime to the rest.

      It's very easy to prove for particular cases, like two numbers (heh!), three numbers, four numbers, etc. But egad, its the proof of the general case that is elusive. (Of course!)

      (If a proof were achieved, it would have prime repercussions.)

      Mark
    • Maximilian Hasler
      Google tells you that Pillai conjectured ([P2]) that the following theorem holds: Proposition 1.2. For every integer k 16 there exists a sequence of k
      Message 2 of 5 , Oct 13, 2011
      • 0 Attachment
        Google tells you that

        Pillai conjectured ([P2]) that the following theorem holds:

        Proposition 1.2. For every integer k > 16 there exists a sequence of k
        consecutive integers
        without a number relatively prime to all others.

        The conjecture was later proven by both Alfred Brauer in [AB] and
        Pillai in [P3].

        You can see AB's proof here :

        http://www.ams.org/journals/bull/1941-47-04/S0002-9904-1941-07455-0/S0002-9904-1941-07455-0.pdf

        Maximilian




        On Thu, Oct 13, 2011 at 8:43 PM, Mark <mark.underwood@...> wrote:
        >
        > I have no doubt that others are familiar with this, but I can't recall encountering it before.  It's a very simple (I like simple!) observation:
        >
        > Given two or more consecutive numbers greater than 1, at least one of them will be relatively prime to the rest.
        >
        > It's very easy to prove for particular cases, like two numbers (heh!), three numbers, four numbers, etc.  But egad, its the proof of the general case that is elusive. (Of course!)
        >
        > (If a proof were achieved, it would have prime repercussions.)
        >
        > Mark
        >
        >
        >
        > ------------------------------------
        >
        > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
        > The Prime Pages : http://www.primepages.org/
        >
        > Yahoo! Groups Links
        >
        >
        >
        >
      • Jens Kruse Andersen
        ... It s only true for up to 16 numbers and no larger amount. See for example http://www.combinatorics.org/Volume_3/PDF/v3i1r33.pdf This shows a counter
        Message 3 of 5 , Oct 13, 2011
        • 0 Attachment
          Mark wrote:
          > Given two or more consecutive numbers greater than 1, at
          > least one of them will be relatively prime to the rest.

          It's only true for up to 16 numbers and no larger amount.
          See for example http://www.combinatorics.org/Volume_3/PDF/v3i1r33.pdf
          This shows a counter example for the 17 numbers from 2184 to 2000:

          for(a=2184,2200,for(b=2184,2200,if(a!=b&\
          gcd(a,b)>1, print("gcd("a", "b") = "gcd(a,b));break())))
          gcd(2184, 2186) = 2
          gcd(2185, 2190) = 5
          gcd(2186, 2184) = 2
          gcd(2187, 2184) = 3
          gcd(2188, 2184) = 4
          gcd(2189, 2200) = 11
          gcd(2190, 2184) = 6
          gcd(2191, 2184) = 7
          gcd(2192, 2184) = 8
          gcd(2193, 2184) = 3
          gcd(2194, 2184) = 2
          gcd(2195, 2185) = 5
          gcd(2196, 2184) = 12
          gcd(2197, 2184) = 13
          gcd(2198, 2184) = 14
          gcd(2199, 2184) = 3
          gcd(2200, 2184) = 8

          --
          Jens Kruse Andersen
        • Mark
          Thank you Maximilian and Jens. I never would have guessed that very interesting result. I should have gone higher in the length of consecutive numbers I
          Message 4 of 5 , Oct 13, 2011
          • 0 Attachment
            Thank you Maximilian and Jens. I never would have guessed that very interesting result. I should have gone higher in the length of consecutive numbers I examined. But no, I had to rush to a conclusion, even neglecting The Google!

            So, I just Googled it, and see a Prime Curio for the number 10:

            "The largest number N such that any set of N consecutive integers contains at least one integer relatively prime to all other integers in the set. [Rupinski]"

            This looks like it was misplaced, and should be a Curio for 16 instead.

            Thanks again,

            Mark
          • Jens Kruse Andersen
            ... Yes, the quoted curio for 10 is wrong. It is at http://primes.utm.edu/curios/page.php?number_id=126&submitter=Rupinski There is already a right curio for
            Message 5 of 5 , Oct 13, 2011
            • 0 Attachment
              Mark wrote:
              > So, I just Googled it, and see a Prime Curio for the number 10:
              >
              > "The largest number N such that any set of N consecutive integers
              > contains at least one integer relatively prime to all other integers in the
              > set. [Rupinski]"
              >
              > This looks like it was misplaced, and should be a Curio for 16 instead.

              Yes, the quoted curio for 10 is wrong. It is at
              http://primes.utm.edu/curios/page.php?number_id=126&submitter=Rupinski

              There is already a right curio for 17 here:
              http://primes.utm.edu/curios/page.php?number_id=15&submitter=Pillai
              "In any set of k < 17 consecutive integers there is always one which is
              relatively prime to all the others. [Pillai]"

              --
              Jens Kruse Andersen
            Your message has been successfully submitted and would be delivered to recipients shortly.