I have a problem with some basic number theory, would appreciate some help!

Hey all,

Given 4a + 9b = n where a and b are nonnegative integers, I need to prove that for n>23 where n is a natural number the equation is always satisfied

In other words,

4a + 9b = 24
4a + 9b = 25
4a + 9b = 26
....

will have a set of nonnegative integer solutions (a,b) for n>23.

Why is it that n has to be greater than 23, not 22 or 24?

I feel like this has to do with the fact that 4 and 9 are coprime but that is all I could think of.

I spend hours trying to figure out how to work this out but I can't seem to figure out so I would ask for some help here..

Reply 1

ghostwalker

17

Original post by standkakao

Hey all,

Given 4a + 9b = n where a and b are nonnegative integers, I need to prove that for n>23 where n is a natural number the equation is always satisfied

In other words,

4a + 9b = 24
4a + 9b = 25
4a + 9b = 26
....

will have a set of nonnegative integer solutions (a,b) for n>23.

Why is it that n has to be greater than 23, not 22 or 24?

I feel like this has to do with the fact that 4 and 9 are coprime but that is all I could think of.

I spend hours trying to figure out how to work this out but I can't seem to figure out so I would ask for some help here..

May not be the most elegant method.

Any integer can be written in the form 4k+i, where

i\in\{0,1,2,3\}

Suppose there is a solution pair (a,b), for 4k+i, then is there a solution pair for 4(k+1) +i ?

Can you take it from there?

As to n>23: Is there a solution for n=23?

(edited 8 years ago)

Reply 2

Math12345

14

https://www.cs.cmu.edu/~adamchik/21-127/lectures/divisibility_5_print.pdf

Page 6,7 might help

Reply 3

Renzhi10122

11

Original post by standkakao

Hey all,

Given 4a + 9b = n where a and b are nonnegative integers, I need to prove that for n>23 where n is a natural number the equation is always satisfied

In other words,

4a + 9b = 24
4a + 9b = 25
4a + 9b = 26
....

will have a set of nonnegative integer solutions (a,b) for n>23.

Why is it that n has to be greater than 23, not 22 or 24?

I feel like this has to do with the fact that 4 and 9 are coprime but that is all I could think of.

I spend hours trying to figure out how to work this out but I can't seem to figure out so I would ask for some help here..

The reason why n>23 is because of the chicken nugget theorem (it has a proper name, but I have no idea what it is). It just says that the largest integer not expressible as ax+by for fixed positive coprime integers a,b and non negative integers x,y is ab-a-b. In fact, your question is basically just the chicken nugget theorem, so if you want more info, that's what to search for.