Just beginning in Discrete math stumbled into the symbolic logic section and need some selp on this question, any input is appreciated.
$$ \forall x \in {Z}, \exists y , z \in {Z} [x = 5y + 7z] $$
Determine whether this statement is true or false.
$\endgroup$ 43 Answers
$\begingroup$Since $\gcd(5,7) = 1$, there exist $m,n$ such that $5m+7n = 1$. And every integer can be written as a sum of $1$ or $-1$.
$\endgroup$ 3 $\begingroup$The statement is true.
Given $x\in\mathbb{Z}$, choose:
- $y=\color\red{+3x}\in\mathbb{Z}$
- $z=\color\green{-2x}\in\mathbb{Z}$
Then $x=15x-14x=5\cdot(\color\red{+3x})+7\cdot(\color\green{-2x})=5y+7z$.
$\endgroup$ 1 $\begingroup$Take for example:
$$760 = 5\cdot 12 + 7 \cdot 100$$
For this, $760$ has a solution $(12, 100)$. Can you find a solution for $765$ ? What about $770$ ? What about $755$? What about a general $760 + 5k$ ?
If, knowing how to find a solution for $x$, you also can find a solution for $x \pm 5$, then it suffices to find a solution for the 5 cases : $x = 0, x = 1, x = 2, x = 3$, and $x = 4$.
$\endgroup$
