Is Every Integer Composition into Relatively Prime Parts a Multiple of Three?

[TimNguyen]

Hello.

I was reading a journal and an interesting problem came up. I believe the journal was in the American Mathematics Society publications. Well, here's the statement.

"For all integers, n greater than or equal to 3, the number of compositions of n into relatively prime parts is a multiple of 3."

Example : For 4: the compositions of relatively prime parts are:

(1,3), (3,1), (2,1,1), (1,2,1), (1,1,2), (1,1,1,1).

This is what I have so far for a "proof":

Let n be an integer greater than or equal to 3.
Then the first composition will be given by (n-1, 1), (1, n-1); since for all k, an integer, (k, 1) and (1, k) are always relatively prime.
Also, (1, 1, ..., 1) where the composition adds to n is also an obtainable composition.

(So basically, I've gotten the end points of the compositions to be a multiple of 3, then I need to prove that the "in-between" compositions will also be a multiple of 3.)

Well, obviously I'm stuck there. I've tried to split it into two cases afterwards where the cases involve n - odd and n - even but it has come to no avail. Also I've tried to find a formula where the compositions of relatively prime parts is a multiple of 3 but it fails at "6". Here was the formula I came up with that failed, if it could be potentially be improved upon.

Formula: Starting at n=1, where i=3, i being the starting point.

(i)!/2^n

Like:
For 3, 3! = 6 divided by 2^1 = 2 will equal 3 compositions- a multiple of 3
For 4, 4! = 24 divided by 2^2 = 4 will equal 6 compositions - a multiple of 3
For 5, 5! = 120 divided by 2^3 = 8 will equal 15 compositions - multiple of 3

Well, hopefully people will post their ideas...

 

[anathema]

Hello,

Thank you for sharing this interesting problem from the journal. I can see that you have made some progress in trying to prove the statement, but I would like to offer some suggestions and insights that may help you in your proof.

Firstly, your approach of starting with the end points (n-1, 1) and (1, n-1) is a good start, but it only covers the cases where n is odd. In order to prove the statement for all integers n, you will need to consider the cases where n is even as well.

One way to approach this problem is to use mathematical induction. This method involves proving the statement for a base case, which in this case could be n=3, and then assuming the statement is true for some integer k, and proving it for k+1. This will then show that the statement is true for all integers greater than or equal to 3.

Another approach could be to consider the prime factorization of n. Since we are dealing with relatively prime parts, we can assume that the prime factors of n are not repeated in any of the compositions. This means that for each prime factor, we can only use it once in a composition. Using this information, you can try to come up with a formula or a general rule that shows that the number of compositions will always be a multiple of 3.

I also noticed that your formula fails for n=8, where the number of compositions is 12, not a multiple of 3. This is because your formula does not take into account the number of ways the prime factors can be distributed among the compositions.

I hope these suggestions help you in your proof. Keep exploring and trying different approaches, and I'm sure you will come up with a solid proof for this statement. Good luck!

 

[quicknote]

Hello, thank you for sharing this interesting problem! I am a scientist and I would be happy to provide a response to your question.

Firstly, I would like to clarify that the statement you have provided is actually a well-known result in number theory known as the Euler's totient function. It states that for any positive integer n, the number of positive integers less than or equal to n that are relatively prime to n is equal to n multiplied by the product of (1-1/p) where p ranges over all the prime factors of n.

Now, let's move on to the proof. Your approach of starting with the end points and trying to prove that the "in-between" compositions are also a multiple of 3 is a good start. To continue with this approach, we can use induction.

For n=3, we have (2,1), (1,2), (1,1,1) as the compositions of relatively prime parts, which is a multiple of 3.

Assuming that for n=k, the number of compositions of relatively prime parts is a multiple of 3, we need to prove that it holds true for n=k+1.

For n=k+1, the first composition will be (k,1), (1,k), which is a multiple of 3 by our assumption. Now, we need to show that the "in-between" compositions are also a multiple of 3.

Let's consider the composition (a,b), where a+b=k+1. Since a and b are relatively prime, their product must be a multiple of 3. This can be broken down into two cases:

1. If a and b are both multiples of 3, then the product ab is a multiple of 3.
2. If one of a or b is a multiple of 3, then the other must be relatively prime to 3. This means that the other number must be either 1 or 2. Therefore, the product ab will again be a multiple of 3.

Hence, all the "in-between" compositions will also be a multiple of 3. This completes the induction step and proves that for all integers n greater than or equal to 3, the number of compositions of n into relatively prime parts is a multiple of 3.

As for your formula, (i)!/2^n, it is not valid for all values of n. For example, for n=6