2
$\begingroup$

Statement 1: any integer no less than four can be factorized as a linear combination of two and three.

Statement 2: any integer no less than six can be factorized as a linear combination of three, four and five.

I tried for many numbers, it seems the above two statement are correct. For example,

4=2+2; 5=2+3; 6=3+3+3; ...

6=3+3; 7=3+4; 8=4+4; 9=3+3+3; 10=5+5; ...

Can they be proved?

  • 0
    There's [partition](http://en.wikipedia.org/wiki/Partition_(number_theory)), but I guess *decompose* is the proper word.2012-08-03

4 Answers 4

3

The question could be generalized, but there is a trivial solution in the given cases.

  1. Any even number can be written as $2n$. For every odd number $x > 1$, there exists an even number $y$ such that $y+3 = x$.

  2. Likewise, numbers divisible by $4$ can be written as $4n$. All other numbers over $2$ are $4n + 5$, $4n + 3$ or $4n + 3 + 3$.

3

Statement 1: Either $b$ is even or $b-3$ is even.

Statement 2: Either $b$ is divisible by 3, or $b-4$ is or ... now complete the argument.

1

Hints:

  1. Use the division algorithm: $n=2q+r.$ What are the values of $r$? If $n≥4,$ then $q≥2,$ and we can re-write $n$ as: $n=2(q−1)+2+r.$ What are the values of $2+r$?

  2. Again use the division algorithm: $n = 3q + r,$ and with $n ≥ 6,$ we have $n = 3(q-1) + 3 + r.$ What are the possible values for $3 + r$?

1

Read part 1.2 of this book:

http://shoup.net/ntb/ntb-v2.pdf

..on Ideals. An Ideal is the set of integers that can be expressed as multiples of some constant k. Let this be $I_k$

Your question is whether $I_2 + I_3 = \mathbb{Z}$

It can be shown that $I_a + I_b = I_{\gcd(a,b)}$

And easily shown that $I_1 = \mathbb{Z} $