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
    Hint: look for their GCD. https://en.wikipedia.org/wiki/Greatest_common_divisor#Properties2012-08-02
  • 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?2012-08-02
  • 0
    In statement 1, read: every integer $\geqslant2$. In statement 2, read: every integer $\geqslant3$.2012-08-02
  • 0
    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.2012-08-02
  • 0
    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?2012-08-02
  • 0
    They're correct expect that the verb "factor" (American) or "factorise" (British) or "factorize" would normally be used when you're talking about multiplying rather than adding.2012-08-02
  • 0
    @Arthur Fischer: Yes, that's what I mean. Maybe the phrase 'linear combination' is inappropriate here.2012-08-03
  • 0
    @MichaelHardy: In fact, I am not sure about the terminology here. If 'factorize' is for multiplying, then what terminology is for adding? In the question I asked, it should be a adding case, right?2012-08-03
  • 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} $