Proof (2nm +3m is a multiple of 7)?

Question

I am not vary good with proofs and i need some help. How can i prove if this given preposition is true or false? $\exists n \forall m (2nm + 3m \text{ is a multiple of 7})$

Answer 1

From your statement $\exists n \forall m$, if we can construct an $n$ such that $7 | 2nm + 3m$, we have a proof. From our formula $$2nm + 3m = m(2n+3)$$ If we take $n=2$, we have a solution since $$m(2(2)+3)=m(7)=7m\\7|7m, \forall m \quad \square$$

Answer 2

Way 1: lucky guess. Suppose it's true, then we can try to name some $n$. $2nm+3m=(2n+3)m=7k$... let's try $n=2$, then if $\forall m (2*2*m+3*m \text{ is a multiple of } 7)$ the initial statement is true. But $2*2*m+3*m=7*m$ which always is a multiple of 7, q.e.d.

Way 2: exhaustive search. Let $P(n,m)$ be "$2nm+3m$ is a multiple of $7$". Note that $P(n,m) = P(n+7,m) = P(n,m+7)$.

Let $Q(n)$ be "$\forall m, P(n,m)$". It is false if there is such $m$ that $\neg P(n,m)$ and is true otherwise. $Q(n) = Q(n+7)$, since if $m : \neg P(n,m)$ then $\neg P(n+7,m)$ and vice versa.

Finally, let $S$ be "$\exists n:Q(n)$". To find whether $S$ is true, we need to check for different $n$ until $Q(n)$ (then $S$ is true) or we check all possible $n$ (and then $S$ is false). The latter part is a bit hard for natural numbers (as opposed to boolean values in predicate logic), but since $Q(n)=Q(n+7)$ we need to check only $n \in \{0,1,2,3,4,5,6\}$. To find whether $Q(n)$ is true for given $n$, we need to check different $m$ until $\neg P(n,m)$ (then $Q(n)$ is false) or we check all possible $m$ (and then $Q(n)$ is true). Since $P(n,m)=P(n,m+7)$, we need to check only $m \in \{0,1,2,3,4,5,6\}$. To find whether $P(n,m)$ is true we need to compute $2nm+3m$ and check if it is a multiple of 7.

All in all, as you can see, after finite number of "elementary" steps we can tell whether $S$ is true. Note that there are theorems of natural arithmetic for which such resolving procedure is potentially infinite (and no finite procedure can be constructed).