# Fractions

royalchicken
Posers and Puzzles 05 Jun '04 00:22
1. royalchicken
CHAOS GHOST!!!
05 Jun '04 00:22
All the numbers to follow are positive integers ðŸ˜›.

For what n is it possible to express n/M as the sum of two fractions with numerator 1 for all M? For what M, for each n, is this decoposition unique?

For example, it is possible for n = 1, and if M is prime the decomposition is unique (are there nonprimes for which it is)?
2. Acolyte
05 Jun '04 00:25
Originally posted by royalchicken
All the numbers to follow are positive integers ðŸ˜›.

For what n is it possible to express n/M as the sum of two fractions with numerator 1 for all M? For what M, for each n, is this decoposition unique?

For example, it is possible for n = 1, and if M is prime the decomposition is unique (are there nonprimes for which it is)?
Does k/1 count as a fraction?
3. royalchicken
CHAOS GHOST!!!
05 Jun '04 00:28
Yes, but it will only help you sometimes. Since you took STEP in 2002, you've done a special case of this problem unless you're one of those silly people who even attempts the mechanics ones ðŸ˜•.
4. Acolyte
05 Jun '04 00:36
Originally posted by royalchicken
Yes, but it will only help you sometimes. Since you took STEP in 2002, you've done a special case of this problem unless you're one of those silly people who even attempts the mechanics ones ðŸ˜•.
In that case, it doesn't work for n at least 3.

For n=2, there's the obvious decomposition 2/M = 1/M + 1/M. Similarly 1/M = 1/2M + 1/2M.

As for uniqueness, I'll have to think about that. (I don't remember much about STEP)
5. royalchicken
CHAOS GHOST!!!
05 Jun '04 00:411 edit
You're right; I made a mistake by saying 'two'. Take that away and you can at least get it big enough since, eg, the harmonic series diverges.

I should also say that they go in lowest terms.

If you leave the 'two' bit, you can still have the parts be distinct though, rather than the 'obvious' 1/m + 1/m...
6. 06 Jun '04 01:26
Originally posted by royalchicken
You're right; I made a mistake by saying 'two'. Take that away and you can at least get it big enough since, eg, the harmonic series diverges.

I should also say that they go in lowest terms.

If you leave the 'two' bit, you can still have the parts be distinct though, rather than the 'obvious' 1/m + 1/m...
Without the &quot;two&quot; bit, n=1 is a trivial solution

1/1 = 1/1
1/2 = 1/2
etc
7. royalchicken
CHAOS GHOST!!!
06 Jun '04 02:43
Originally posted by iamatiger
Without the "two" bit, n=1 is a trivial solution

1/1 = 1/1
1/2 = 1/2
etc
Okay, my bad. By removing the 'two' bit I meant to imply 'two or more', but it really isn't clear.
8. Acolyte
06 Jun '04 08:04
Originally posted by royalchicken
Okay, my bad. By removing the 'two' bit I meant to imply 'two or more', but it really isn't clear.
As in 'two or more distinct'? Otherwise we have n/M = (1/M n times) for n&gt;1.
9. TheMaster37
Kupikupopo!
06 Jun '04 17:36
It DOES work for some n&gt;=3

3/12 = 1/6 + 1/12

7/24 = 1/4 + 1/24
10. royalchicken
CHAOS GHOST!!!
07 Jun '04 02:41
Well, I wanted lowest terms, so 3/12 is right out.
11. 07 Jun '04 07:20
Originally posted by royalchicken
Okay, my bad. By removing the 'two' bit I meant to imply 'two or more', but it really isn't clear.
42
12. Acolyte
08 Jun '04 08:54
OK, I think I can do this indirectly. I'm assuming 'two or more (but finitely many) distinct' below.

Let f(1) = 1/2, 1/3, 1/6
f(1/(n-1)) = 1/n, 1/n(n-1) for n &gt; 2.

Then f decomposes 1/k into distinct fractions with numerator 1 and larger denominator.

Let S1 = f(1).

By applying f repeatedly to the terms in Sn and the resulting terms, we can obtain another decomposition S(n+1) of 1 that does not involve the terms of S1, ..., Sn. Hence we can decompose any natural number n by induction, by combining S1, ..., Sn. Now multiply the denominator of each term in the resulting decomposition by M, and we have a decomposition of n/M. This decomposition is not unique, as we can certainly apply f to the term with the highest denominator to get a different decomposition satisfying the conditions.
13. Acolyte
08 Jun '04 10:301 edit
Now for the 'exactly two distinct' case:

Suppose n/M = 1/ck + 1/dk, where c and d are coprime and aren't both 1
&lt;=&gt; cdkn = M(c+d)

Now cd, c+d are coprime; n, M are coprime
&lt;=&gt; cd|M, (c+d)|kn, n|(c+d), M|cdk
&lt;=&gt; cdp = M, nq = (c+d), k = pq

So a decomposition is possible iff we can find coprime factors of M whose sum is a multiple of n (then we can choose k,p,q to fit).

I can't think of a general answer right now, but two things are immediate:
n = 1: decomposition is always possible
M prime: decompositions, if they exist, are unique

Come to think of it,
n = 1: since we can choose any pair of factors, if M is composite then the decomposition is not unique.
n = 2: decomposition is possible for M &gt; 2, since M must have an odd factor f greater than 1, and f+1 is even. The decomposition is unique iff these are the only two odd factors of M =&gt; M is a power of 2 times a prime =&gt; M is prime.