For $n\geq8$ prove that $n=5p+3q$ exists. 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$
 A: 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.

A: Induction hint:


*

*$A_{8}=\{5,3\}$

*$A_{9}=\{3,3,3\}$

*$A_{10}=\{5,5\}$

*$A_{n+3}=A_{n}\cup\{3\}$

A: 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}

A: 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.
