For $n\geq8$ prove that $n=5p+3q$ exists.

Question

Can you give me some tips on the following problem:

For every $n\geq8$ prove that there exist natural numbers $p,q$ so that: $n = 5p + 3q$

Answer 1

With explicit construction for $p$ and $q$:

Write $n=8k+l$, $k\geq 1$ and $0\leq l<8$. Then $p$ and $q$ can be constructed as follows.

• $l=0$: $n=5k+3k$,
• $l=3,6,5$: $n=5k+3(k+1)$, $n=5k+3(k+2)$, and $n=5(k+1)+3k$, respectively
• $l=2,7$: $n=5(k+1)+3(k-1)$ and $n=5(k+2)+3(k-1)$, respectively
• $l=1,4$: $n=5(k-1)+3(k+2)$ and $n=5(k-1)+3(k+3)$, respectively.

Answer 2

Induction hint:

• $A_{8}=\{5,3\}$
• $A_{9}=\{3,3,3\}$
• $A_{10}=\{5,5\}$
• $A_{n+3}=A_{n}\cup\{3\}$

Answer 3

Denote the statement that you want to show as $P(n)$ and proceed by induction

• Base case: $n=8$. Then: $8=5\cdot(1)+3\cdot(1)$, so $P(8)$ holds with $p=q=1$.
• Induction hypothesis: $P(n)$ holds for some $n\in\mathbb N, n>8$.
• Induction step: Show that $P(n+1)$ holds as well. Since $P(n)$ holds, there are $p,q \in \mathbb N$ such that $n=5p+3q$. Hence \begin{align}n+1&=5p+3q+1\\[0.2cm]&=5(p-1)+3(q+1)+5-3+1\\[0.2cm]&=5(p-1)+3(q+1)+3=5(p-1)+3(q+2)\end{align} To go from the first to the second line, I implicitly assumed that $p\ge 1$, since otherwise $p-1<0\notin \mathbb N$. If $p=0$, then necessarily $q\ge 3$, hence \begin{align}n+1&=5(0)+3q+1=3(q-3)+9+1\\[0.2cm]&=3(q-3)+10=5(2)+3(q-3)\tag{qed}\end{align}

Answer 4

Let $\mathbb N$ denote the set of natural numbers.

I preassume that $0\in\mathbb N$ which finds its justification in the fact that $9$ cannot be written as $5p+3q$ if $p,q$ are both demanded to be positive integers.

Defining $A:=\{5p+3q\mid p,q\in\mathbb N\}$ it is to be shown that $\{n\in\mathbb N\mid n\geq8\}\subseteq A$.

Observe that $A$ is closed under addition: if $a,b\in A$ then $a+b\in A$.

By brute force it can be proved that $8,9,10,11,12,13,14,15\in A$.

This is the base step of proving with induction that $n\in A$ is true for every $n\geq8$.

If $n\geq16$ then $n=(n-8)+8\in A$.

This because both terms are elements of $A$ and $A$ is closed under addition.