Least Positive Integer N for 4a+7b Form: Prove Property

[Bleys]

Homework Statement

Find the least positive integer N such that every integer $$n \geq N$$ can be written in the form 4a + 7b, where a,b are non-negative integers. Prove your N has this property

Homework Equations

The Attempt at a Solution

Well, I kind of went about doing trial and error. I know 17 is not such a number, but 18,19,20,21,22 are. I figured I'd use (strong) induction. Suppose it's true for all $$22 \leq k \leq n$$. Consider now $$18 \leq n+1 -4 < n$$. By the induction hypothesis n+1 -4 = 4a + 7b, so n+1 = 4(a+1) +7b, for some non-negative a,b.

Is this correct? What if I wanted to do it more generally. That is, if gcd(x,y)=1 find N such that, for all $$n \geq N$$, n can be written as xa+yb, for non-negative a,b?

 

[rasmhop]

That is correct.

The general case is a little harder as we can't just use trial and error and confirm our observations. I will give you a sketch here of how to show that N=(x-1)(y-1) (especially the second part is pretty vague, but you can just ask if you're having trouble figuring it out).

First to show that N must be at least (x-1)(y-1) assume that there exists non-negative integers a,b such that:
ax + by = (x-1)(y-1)-1
Then (a+1 - y)x + (b + 1)y = 0 so x | b+1, and therefore $b \geq x-1$ and similarly $a \geq y-1$. Use these inequalities and ax+by = (x-1)(y-1) - 1 to obtain a contradiction and thereby showing N must be at least (x-1)(y-1).


Assume without loss of generality x > y. Let r be an integer in {0,1,...,y-2}. Then
$$(y-2)x \leq (x-1)(y-1)+r$$
You can show that there exists an integer a in {0,1,...,y-2} such that
$$(y-1)(x-1) +r \equiv ax \pmod y$$
[HINT: 0x, 1x, 2x, ..., (y-2)x represents all residue classes modulo y except the residue class of -x]
and use this to find a non-negative integer b such that (x-1)(y-1)+r = ax + by. This shows (x-1)(y-1)+r can be expressed as a linear combination of x and y with positive coefficients for r in {0,1,...,y-2}. We now only need to show it for r=y-1, but then (x-1)(y-1) + r = x(y-1).

 

[Bleys]

That last part I don't understand.
How do you deduce from the inequality that there is an integer a with that property? I'm sorry if it should be obvious..

 

[rasmhop]

The inequality isn't actually used to find a suitable a, but rather to ensure that when we do the b we choose will be non-negative.

0x, 1x, 2x, ..., (y-2)x, (y-1)x represent all residue classes modulo y. Therefore (x-1)(y-1)+r must be congruent to one of these modulo y. So we get that for some a in {0,1,...,y-1} we have:
$$(x-1)(y-1)+r \equiv ax \pmod y$$
a could not be y-1 because then we would have (using that y-1 is congruent to -1 modulo y):
$$-x \equiv (y-1)x = ax \equiv (x-1)(y-1)+r \equiv -x+1+r \pmod y$$
Cancelling we get $1+r \equiv 0 \pmod y$, but this is a contradiction since r+1 is in {1,2,...,y-1}.

 

[Bleys]

Ok, thank you!