Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Hint: look for their GCD. en.wikipedia.org/wiki/Greatest_common_divisor#Properties –  Andrew Aug 2 '12 at 15:55
3  
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? –  Arthur Fischer 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
show 5 more comments

4 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
Thanks! This explanation is very easy for me to understand. –  Shiyu Aug 3 '12 at 9:38
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
Let me know if you have further questions. –  user2468 Aug 2 '12 at 16:15
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.