91Ó°ÊÓ

Let \(a, b,\) and \(c\) be integers with \(a \neq 0\) and \(b \neq 0,\) and let \(d=\operatorname{gcd}(a, b)\). If \(d\) does not divide \(c\), then the linear Diophantine equation \(a x+b y=c\) has no solution.

(a) Let \(a\) and \(b\) be nonzero integers. If there exist integers \(x\) and \(y\) such that \(a x+b y=1,\) what conclusion can be made about \(\operatorname{gcd}(a, b) ?\) Explain. (b) Let \(a\) and \(b\) be nonzero integers. If there exist integers \(x\) and \(y\) such that \(a x+b y=2,\) what conclusion can be made about \(\operatorname{gcd}(a, b) ?\) Explain.

(a) Find integers \(u\) and \(v\) such that \(9 u+14 v=1\) or explain why it is not possible to do so. Then find integers \(x\) and \(y\) such that \(9 x+14 y=10\) or explain why it is not possible to do so. (b) Find integers \(x\) and \(y\) such that \(9 x+15 y=10\) or explain why it is not possible to do so. (c) Find integers \(x\) and \(y\) such that \(9 x+15 y=3162\) or explain why it is not possible to do so.

Is the following proposition true or false? Justify your conclusion. $$ \text { If } n \in \mathbb{N}, \text { then } \operatorname{gcd}(5 n+2,12 n+5)=1 \text { . } $$

(a) Determine five different primes that are congruent to 3 modulo 4 . (b) Prove that there are infinitely many primes that are congruent to 3 modulo \(4 .\)

The Twin Prime Conjecture states that there are infinitely many twin primes, but it is not known if this conjecture is true or false. The answers to the following questions, however, can be determined. (a) How many pairs of primes \(p\) and \(q\) exist where \(q-p=3\) ? That is, how many pairs of primes are there that differ by 3 ? Prove that your answer is correct. (One such pair is 2 and \(5 .\) ) (b) How many triplets of primes of the form \(p, p+2,\) and \(p+4\) are there? That is, how many triplets of primes exist where each prime is 2 more than the preceding prime? Prove that your answer is correct. Notice that one such triplet is \(3,5,\) and 7

Square Roots and Irrational Numbers. In Chapter \(3,\) we proved that some square roots (such as \(\sqrt{2}\) and \(\sqrt{3}\) ) are irrational numbers. In this activity, we will use the Fundamental Theorem of Arithmetic to prove that if a natural number is not a perfect square, then its square root is an irrational number. (a) Let \(n\) be a natural number. Use the Fundamental Theorem of Arithmetic to explain why if \(n\) is composite, then there exist distinct prime numbers \(p_{1}, p_{2}, \ldots, p_{r}\) and natural numbers \(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{r}\) such that $$ n=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{r}^{\alpha_{r}} $$ Using \(r=1\) and \(\alpha_{1}=1\) for a prime number, explain why we can write any natural number greater than one in the form given in equation (1). (b) A natural number \(b\) is a perfect square if and only if there exists a natural number \(a\) such that \(b=a^{2}\). Explain why \(36,400,\) and 15876 are perfect squares. Then determine the prime factorization of these perfect squares. What do you notice about these prime factorizations? (c) Let \(n\) be a natural number written in the form given in equation (1) in part (a). Prove that \(n\) is a perfect square if and only if for each natural number \(k\) with \(1 \leq k \leq r, \alpha_{k}\) is even. (d) Prove that for all natural numbers \(n,\) if \(n\) is not a perfect square, then \(\sqrt{n}\) is an irrational number. Hint: Use a proof by contradiction.