# Thread: Math Counts Number Theory

1. ## Math Counts Number Theory

a) if a and b must be nonnegative integers, what is the largest integer n such that 13a +18b =n has no solutions?

b) if a and b must be positive integers, what's the largest integer n such that 13a + 18b = n has no solution?

c) What's the difference between the two above?

2. See here

3. Originally Posted by jj1004
a) if a and b must be nonnegative integers, what is the largest integer n such that 13a +18b =n has no solutions?

b) if a and b must be positive integers, what's the largest integer n such that 13a + 18b = n has no solution?

c) What's the difference between the two above?
It is easy to see that 13(7)- 5(18)= 91- 90= 1. We can write that as 13(7)+ 18(-5)= 1 and so, for any integer n, 13(7n)+ 18(-5n)= n. That is, one solution is a= 7n and b= -5n. But, of course, those are not non-negative. We can, however, also see that, for any integer k, a= 7n- 18k, b= -5n+ 13k is also a solution: 13(7n- 18k)+ 18(-5n+ 13k)= 91n- (13)(18)k- 90n+ 18(13)k so the "k" terms cancel.

In order to have non-negative solutions, we must have $a= 7n- 18k\ge 0$ and [tex]b= -5n+ 13k\ge 0[/itex]. Those together say that $\frac{5n}{13}\le \frac{7n}{18}. The problem has non-negative solutions if and only if there is an integer between those two fractions.

That will certainly be true if the distance between them is at least 1: if
img.top {vertical-align:15%;} $\frac{7n}{18}- \frac{5n}{13}= \frac{n}{234}\ge 1$ which means that there will always be a solution if $n\ge 234$. The largest n such that the problem has non-negative solutions must be less than that.

Now look at [math\frac{7n}{18}" alt="\frac{5n}{13}\le \frac{7n}{18}. The problem has non-negative solutions if and only if there is an integer between those two fractions.

That will certainly be true if the distance between them is at least 1: if $\frac{7n}{18}- \frac{5n}{13}= \frac{n}{234}\ge 1$ which means that there will always be a solution if $n\ge 234$. The largest n such that the problem has non-negative solutions must be less than that.

Now look at [math\frac{7n}{18}" /> and $\frac{5n}{13}$ for n= 233, 232, 231, downward, until you find a value of n so that those two fractions do NOT have an integer between them. The first such value is the largest n such that that problem has non-negative solutions.

If a and b are required to be positive, change " $\le$" to "= ". Now look for an n such that $\frac{7n}{18}$ and $\frac{5n}{13}$ have an integer strictly between them- that neither of the fractions is itself an integer. Of course, there is no need to repeat the calculations you did the first time. If the answer you got for the first problem did NOT make either of the fraction an integer (so that neither a nor b was 0) that is also the answer to the second problem. If the answer you got for the first problem made one of the fractions an integer (so that a or b was 0) you need to continue taking smaller values of n.