# Are the two statements concening number theory correct?

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?

-
Hint: look for their GCD. en.wikipedia.org/wiki/Greatest_common_divisor#Properties – Andrew Aug 2 '12 at 15:55
By a linear combination of $2$ and $3$ do you perhaps mean something of the form $2a + 3b$ where $a$ and $b$ are non-negative integers? – arjafi Aug 2 '12 at 15:57
In statement 1, read: every integer $\geqslant2$. In statement 2, read: every integer $\geqslant3$. – Did Aug 2 '12 at 16:00
I wouldn't use the word factorize, since that means breaking down into a product of factors. Instead, an integer can be written or described as a linear combination, or perhaps decomposed into a linear combination. – Théophile Aug 2 '12 at 16:18
For first, can you see that as soon as you find two consecutive numbers that are representable, the rest are? For second, can you see that as soon as you find three consecutive numbers that are representable, the rest are? – André Nicolas Aug 2 '12 at 16:38

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

-
Thanks! This explanation is very easy for me to understand. – Shiyu Aug 3 '12 at 9:38

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.

-

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$?

-
Let me know if you have further questions. – user2468 Aug 2 '12 at 16:15

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}$

-