Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

On partitioning an even number into a pair of (relative) primes

  1. Oct 18, 2014 #1

    Marchal

    User Avatar
    Gold Member

    An example:


    For m= 176 (132<176<172 one finds


    r=(3-2)x(5-2)x(7-2)x(11-1)x(13-2)=1650 relative primes (0<v<2x3x5x7x11x13),


    forming 825 asymmetric pairs, among them four partitions into prime numbers:


    19+157, 37+139, 67+109, 73+103, 79+97.
     

    Attached Files:

  2. jcsd
  3. Oct 18, 2014 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I don't understand your notation at all. It is different from standard mathematics, so you have to make clear what you mean.
    176<172 is wrong, and what does the comparison of a number and a vector in the pdf mean?
    What do you want to discuss?

    What does this have to do with 176? And which numbers are relative primes?
    Pairs of what?
    Maybe, but you won't find 825 different sums, as 1+175, 2+174, ..., 88+88 just leads to 88 different sums.
     
  4. Oct 20, 2014 #3

    Marchal

    User Avatar
    Gold Member

    Thanks for commenting, mfb! I try to correct/improve this thread as follows:


    Take as an example m=176, which admits 11 as a divisor, but none of the primes 3, 5, 7, 13.

    Then the expression r=(3-2)x(5-2)x(7-2)x(11-1)x(13-2)=1650 means that
    In the interval (0<n<2x3x5x7x11x13) there are exactly 1650 numbers with the properties:

    (1) they are relative primes with regard to the prime numbers (2, 3, 5, 7, 11, 13),

    (2) Out of these 1650 numbers, 825 pairs a, b can be selected to form partitions a+b≡176 (mod 2x3x5x7x11x13).

    Now the Statement:

    Because 132<176<172 the partitions of 176 into (absolute) prime numbers form a non-empty subset (of the 825 partitions into relative primes).

    On the basis of the relative primes with regard to all prime numbers pi pr the reasonment can be applied to any even number
    m (m>10, pr2<m<pr+12)


    Attempting to falsify the statement:

    According to (2), each of the 825 partitions must sum up to either 176 or 176+2x3x5x7x11x13. Assuming none adds up to 176:, we would have

    a+b = 176+2x3x5x7x11x13. (for all a, b). Then:

    - if a<176,
    then b>2x3x5x7x11x13 , which is in contradiction with the existence of a relative prime c= b-2x3x5x7x11x13
    - if a>176 and b>176:, then no prime numbers p<176 could exist apart from 2, 3 ,5, 7, 11, 13 - in contradiction with the distribution law for prime numbers.


    Maybe my "logic" is erroneous. I will be thankful to anybody who might want to analyze my deduction.

    M. Marchal
     
  5. Oct 20, 2014 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I doubt that statement. Why would it be -2 in the factors? Why would that statement depend on 176 at all?

    Take 16 as an example, which has 2 as prime factor, but not 3.
    In the interval 0 < n < 2*3, is there (3-2)=1 number that are relative prime to both 2 and 3? No, there are (2-1)(3-1)=2 numbers, one and five.

    (2) is impossible to check as long as (1) is wrong.

    What is the special relevance of 13 and 17? All numbers are squares of primes or lie between two squares of primes.
     
  6. Oct 22, 2014 #5

    Marchal

    User Avatar
    Gold Member

    Hello mfb

    In the interval (0<n<2x3x5x7x11x13) there are exactly 1650 numbers with the properties:

    (1) they are relative primes with regard to the prime numbers (2, 3, 5, 7, 11, 13),

    Quote:

    I doubt that statement. Why would it be -2 in the factors? Why would that statement depend on 176 at all?

    Take 16 as an example, which has 2 as prime factor, but not 3.
    In the interval 0 < n < 2*3, is there (3-2)=1 number that are relative prime to both 2 and 3? No, there are (2-1)(3-1)=2 numbers, one and five.


    Reply:

    For m=16 we have r=(3-2)=1. In the interval 0 < n < 2*3, five is the only number permitting a partition of 16 (5+11=16 is a partition, while 1+15 is not). Evidently, 11 which is not contained in the interval 0<n< 2x3 is not counted by the product r. But considering the inequalities

    2x3<52-1, 2x3x5<72-1,
    but 2x3x5x7>112, and, certainly 2x3x5x7x ...x pn>pn+12-1

    it becomes clear that for sufficiently large pn (i.e. for pn>5), r will count all rp (rp=relative prime) in the interval 0<n<2x3x...pn.

    The product r contains a factor (p-1) for every odd prime divisor p of the even number m, and a factor (p-2) for every prime number p<pn which is not a prime factor.

    Thus, r is a function of the prime factors of m. It will admit the same value for all even numbers that contain the same prime factors. So we will have r=1650 for m=176=24x11, but also m=22, 44, 66, 88 and even 242=2x112 etc.

    Considering all the odd prime numbers p<pn, r can admit 2n different values, each value of r corresponding to a distinct class of even numbers: any even number belonging to one and only one class.

    For its simplicity the formula for r might have been known for a long time (A.M. Legendre 1752-1833 may have come across it when studying the distribution of numbers which do not contain the first n prime factors), but I did'nt find it in one of my textbooks.

    Because 132<176<172 the partitions of 176 into (absolute) prime numbers form a non-empty subset (of the 825 partitions into relative primes).

    Quote:

    What is the special relevance of 13 and 17?
    Reply:

    For any m with pn2<m<pn+1 2 the rp which are <m will be prime numbers (and there will be two of them at least, partitioning m.

    Dear mfb, excuse me for having to give to you some stuff to examine. And thank you in advance!​


     
  7. Oct 23, 2014 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Now you are mixing different statements. The way you wrote it, the part I quoted (no pairs involved) should be true - but it is not.
    If you want to use (2) as a requirement on the numbers, you need a clear way to do this (see also the problem with 11) without making the statement trivial ("there are as many pairs as this statement because I count pairs until I reach that number").

    That really looks like a made-up rule specifically for this example. Yes it is limited to small numbers, as the product of all primes up to the square root grows faster than the number, but a general rule cannot have any exceptions, otherwise it is not a general rule.


    Up to the square root of m, apparently. So it does depend on the powers of the prime factors, 22 and 242 give different products.

    The classification is trivial. Every function mapping integers on other integers allows that.

    Let me rephrase the question. You said:
    Does that mean every number between 132 and 172 will have that property (the partitions form a non-empty subset)? And numbers outside that range might not? Because that's how you wrote it.
     
  8. Oct 29, 2014 #7

    Marchal

    User Avatar
    Gold Member

    Quote: That really looks like a made-up rule specifically for this example. Yes it is limited to small numbers, as the product of all primes up to the square root grows faster than the number, but a general rule cannot have any exceptions, otherwise it is not a general rule.

    Reply: Right, I was mixing up things. Now, to be precise, and to arrive at a rule valid for any even number m:

    In the formula r=∏(pi-ki) each prime number 3≤pi≤pr appears only once (regardless the power it may have in the factorization of m), with ki =1 if it is a divisor, ki=2, if not.
    r (m) counts the relative primes situated in the interval 0<n<2x∏pi. The prime numbers 3≤pi≤pr are not included in this count.

    Then r/2, or (r-1)/2 (if r is an odd number) counts the partitions into relative primes (a,b):
    a+b≡m (mod 2x∏pi (0<m<2x3x,,,x pr)⇒ a+b=m or a+b=m+2x∏pi.

    Examples:
    m=2<2x3 ⇒ r=3-2=1, (r-1)/2+1=1⇒ one partition 1+1=2
    m=4<2x3 ⇒ r=3-2=1, (r-1)/2+1=1⇒ one partition 5+5=10 (the partition 4=1+3 is not counted)
    m=16<2x3x5⇒ r=(3-2)x(5-2)=3, (r-1)/2+1=2 ⇒ two partitions: 17+29=23+23=46 (the partitions 16=11+5=13+3 are not counted)
    m=18<2x3x5⇒ r=(3-1)x(5-2)=6, r/2=3 ⇒ three partitions: 1+17=7+11=18, 19+29=48 (the "partition" 18=13+5 is not counted, while 1+47=7+41=11+37=17+31=48 have each a component >30)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: On partitioning an even number into a pair of (relative) primes
  1. Prime numbers (Replies: 8)

  2. Prime Numbers (Replies: 1)

Loading...