91Ó°ÊÓ

The difference of any even integer minus any odd integer is odd.

Prove each of the statements in 21-26 in two ways: (a) by contraposition and (b) by contradiction. For all integers \(m\) and \(n\), if \(m+n\) is even then \(m\) and \(n\) are both even or \(m\) and \(n\) are both odd.

Let \(N=2 \cdot 3 \cdot 5 \cdot 7+1\). What remainder is obtained when \(N\) is divided by 2 ? 3 ? 5 ? 7 ? Is \(N\) prime? Justify your answer.

Prove that for all integers \(n, n^{2}-n+3\) is odd.

Suppose \(a\) is an integer and \(p\) is a prime number such that \(p \mid a\) and \(p \mid(a+3)\). What can you deduce about \(p\) ? Why?

Definition: The least common multiple of two nonzero integers \(a\) and \(b\), denoted \(\operatorname{lcm}(a, b)\), is the positive integer \(c\) such that a. \(a \mid c\) and \(b \mid c\) b. for all integers \(m\), if \(a \mid m\) and \(b \mid m\), then \(c \mid m\). Prove that for all positive integers \(a\) and \(b, \operatorname{gcd}(a, b)=\) \(\operatorname{lcm}(a, b)\) if, and only if \(a=b\).

The following "proof" that every integer is rational is incorrect. Find the mistake. "Proof (by contradiction): Suppose not. Suppose every integer is irrational, Then the integer 1 is irrational. But \(1=1 / 1\), which is rational. This is a contradiction. [Hence the supposition is false and the theorem is true.]"

Definition: The least common multiple of two nonzero integers \(a\) and \(b\), denoted \(\operatorname{lcm}(a, b)\), is the positive integer \(c\) such that a. \(a \mid c\) and \(b \mid c\) b. for all integers \(m\), if \(a \mid m\) and \(b \mid m\), then \(c \mid m\). Prove that for all positive integers \(a\) and \(b, a \mid b\) if, and only if, \(\operatorname{lcm}(a, b)=b\).

Show that any integer \(n\) can be written in one of the three forms $$ n=3 q \text { or } n=3 q+1 \text { or } n=3 q+2 $$ for some integer \(q\).

An alternative proof of the infinitude of the prime numbers begins as follows: Proof: Suppose there are only finitely many prime numbers. Then one is the largest. Call it \(p\). Let \(M=p !+1\). We will show that there is a prime number \(q\) such that \(q>p\). Complete this proof.