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

[Marchal]

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.

 

[mfb]

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?

r=(3-2)x(5-2)x(7-2)x(11-1)x(13-2)=1650 relative primes

What does this have to do with 176? And which numbers are relative primes?

forming 825 asymmetric pairs

Pairs of what?

among them four partitions into prime numbers

Maybe, but you won't find 825 different sums, as 1+175, 2+174, ..., 88+88 just leads to 88 different sums.

 

[Marchal]

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 13²<176<17² 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 p_i ≤ p_r the reasonment can be applied to any even number
m (m>10, p_r²<m<p_r+1²)​

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

 

[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),

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.

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

What is the special relevance of 13 and 17? All numbers are squares of primes or lie between two squares of primes.

 

[Marchal]

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<5²-1, 2x3x5<7²-1,
but 2x3x5x7>11², and, certainly 2x3x5x7x ...x p_n>p_n+1²-1

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

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<p_n 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=2⁴x11, but also m=22, 44, 66, 88 and even 242=2x11² etc.

Considering all the odd prime numbers p<p_n, r can admit 2ⁿ 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 p_n²<m<p_n+1 ² 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!​

​

 

[mfb]

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).

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").

Evidently, 11 which is not contained in the interval 0<n< 2x3 is not counted by the product r.

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.

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<p_n which is not a prime factor.

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.

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

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

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 p_n²<m<p_n+1 ² the rp which are <m will be prime numbers (and there will be two of them at least, partitioning m.​

Let me rephrase the question. You said:

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

Does that mean every number between 13² and 17² 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.

 

[Marchal]

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=∏(p_i-k_i) each prime number 3≤p_i≤p_r appears only once (regardless the power it may have in the factorization of m), with k_i =1 if it is a divisor, k_i=2, if not.
r (m) counts the relative primes situated in the interval 0<n<2x∏p_i. The prime numbers 3≤p_i≤p_r 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∏p_i (0<m<2x3x,,,x p_r)⇒ a+b=m or a+b=m+2x∏p_i.

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)