0

Prove that for every integer $n \ge 8$, there exist nonnegative integers $a$ and $b$ such that $n = 3a + 5b$.

Proof: Let $n \in \mathbb Z$ with $n \ge 8$. Then $n = 3q$ where $q \ge 3, n = 3q + 1$ where $q \ge 3$ or $n = 3q + 2$ where $q ≥ 2$. We consider these three cases.

Case 1. $n = 3q$ where $q \ge 3$. Then $n = 3a + 5b$, where $a = q \ge 3$ and $b = 0$.

Case 2. $n = 3q + 1$ where $q \ge 3$. Then $n = 3(q − 3) + 10$, where $q − 3 \ge 0$. Thus $n = 3a + 5b$, where $a = q − 3 \ge 0$ and $b = 2$.

Case 3. $n = 3q + 2$ where $q \ge 2$. Then $n = 3(q − 1) + 5$, where $q − 1 \ge 1$. Thus $n = 3a + 5b$, where $a = q − 1 \ge 1$ and $b = 1$.

For every integer $n \ge 7$, there exist positive integers $a$ and $b$ such that $n = 2a + 3b$.

Proof: Let $n$ be an integer such that $n \ge 7$. Then $n = 2q$ or $n = 2q + 1$ for some integer $q$. We consider these two cases.

Case 1. $n = 2q$. Since $n \ge 7$, it follows that $q \ge 4$. Thus $n = 2q = 2(q − 3) + 6 = 2(q − 3) + 3 \cdot 2$. Since $q \ge 4$, it follows that $q − 3 \in \mathbb N$.

Case 2. $n = 2q + 1$. Since $n \ge 7$, it follows that $q \ge 3$. Thus $n = 2q + 1 = 2(q − 1) + 2 + 1 = 2(q − 1) + 3 \cdot 1$. Since $q \ge 3$, it follows that $q − 1 \in \mathbb N$.

Once the cases are chosen, the proofs are simple. Why do we we use $3$ cases in the first problem and $2$ cases in the second one? And why exactly these cases? Looks like it has to do with the integers in front of $a$ and $b$ in the problem statements. But why does that influence(if it does) the number of cases we choose?

keys
  • 85

1 Answers1

0

Basically we do those cases because they work. The number of cases are just what is needed to cover all the possibilities. In the second case we could also have done three cases on the values for $b$.

It's proably worth noting that doing a proof by cases, you almost always try the fewest number of cases that looks natural from the prolem statement. In the first problem there's no reason to assume it will make things any easier to divide in to even/odd, but as there's a three in there in makes sense to divide on the possible remainders on division by 3.

With more knowledge of the topic at hand, you'll be better a spotting what to divide by, you'll rarely encounter cases where there's no hint in the problem for someone who knows the subject.

Henrik supports the community
  • 6,831
  • They work, but how can we be sure we chose every case we need? – keys Apr 23 '15 at 20:06
  • @keys: For the second one, for instance, every integer $n$ is either of the form $n=2q$ or $n=2q+1$ (according to whether it is even or odd), so every $n \ge 7$ is covered by one of the two cases. Hence our proof applies to every integer $n \ge 7$. The author apparently thought this was obvious enough not to need explanation, but you're right that it is important to consider. – Nate Eldredge Apr 23 '15 at 20:12
  • @ Nate Eldredge, in the first problem, though, we either have two even integers and one odd one or two odd integers and one even integer. That's a little confusing. – keys Apr 23 '15 at 20:15
  • @keys: In the first problem we don't divide in even/odd, but by remainder on division by $3$. I'll add more to the answer on that (it bacame rather long for a comment). – Henrik supports the community Apr 23 '15 at 21:12