MATH 341 Midterm 1

$ \text{An equation whose variables are contained to lie in} \thinspace \mathbb{Z} \thinspace \text{or} \thinspace \mathbb{N} \thinspace \text{is called a diophantine equation}.$

$ \text{Any non-empty subset of} \thinspace \mathbb{Z} \thinspace \text{that is bounded below has a least element.} $
$\text{That is, let S} \subseteq \mathbb{Z} \thinspace \text{be non-empty} \thinspace ( \text{S} \neq \emptyset) \thinspace \text{such that}$

$ \text{there exists z} \in \mathbb{Z} \thinspace \text{such that z<n for all n} \in \text{S}. $

$ \text{Every non-empty subset of} \thinspace \mathbb{Z} \thinspace \text{that is bounded below has a least element}. $

$ \text{Every non-empty subset of} \thinspace \mathbb{Z} \thinspace \text{that is bounded above has a least element}. $

$\text{Let a,b} \in \mathbb{N},\text{there exists q,r} \in \mathbb{Z^+}\thinspace \text{such that a=bq+r and} \thinspace 0 \leq \text{r} < \text{b}.$

$\text{Let a,b} \in \mathbb{Z}. \text{A linear combination of a and b is any integer} \thinspace \text{that can be expressed as ax+by for some x,y}\in \mathbb{Z}. $

$\text{Let a,b}\in \mathbb{Z}. \text{Then (a,b) can be written as a linear combination} \thinspace \text{such that (a,b)=ax+by for some x,y} \in \mathbb{Z} $

$\text{Let a,b} \in \mathbb{Z}, \text{such that} \thinspace \text{a} \neq 0 \thinspace \text{and} \thinspace \text{b} \neq 0. $
$\text{Then the set of linear combinations of a and b is equal to the set of multiples of (a,b).} $

$ \text{A natural number p that is greater than or equal to 2} \thinspace (\exists \text{p}\in \mathbb{N} \thinspace \text{such that p} \geq 2) \thinspace \text{is only prime} $
$\text{if it is divisible by two unique natural numbers 1 and p (itself)}. $

$\text{Let a,b} \in \mathbb{Z}. \thinspace \text{Then a and b are relatively prime}\iff \text{1 is a linear combination of a and b}. $

Two integers are relatively prime if (a,b) =1.

Since 1 is only divisible by 1, by definition of a prime number, 1 cannot be prime.

a|c

False. One such counterexample would be (4,6)=2 but 4x+6y=14 in the case that x=2 and y=1. This statement is only true if d=1.

p|a or p|b

$ \thinspace p = q_\text{j} \thinspace \text{for some} \thinspace \text{j} \in \{1,2,...,\text{n} \}.$

$ \thinspace \text{p}|\text{q}_\text{j}\thinspace \text{for some} \thinspace \text{j} \in \{1,2,...,\text{n} \}.$

$ \text{Every natural number n that is greater than 2} \thinspace (\forall \text{n} \in \mathbb{N} \thinspace \text{such that} \geq 2)$
$ \text{can be expressed uniquely as a prime or product of primes}. $

$\text{That is, there exists a natural number r and prime numbers} \thinspace \text{p}_1,...,\text{p}_\text{r} $
$\text{such that} \thinspace \text{n} = \text{p}_1\text{p}_2...\text{p}_\text{r}.$
$ \text{Moreover,if} \thinspace \text{n} = \text{q}_1\text{q}_2...\text{q}_\text{s} \thinspace \text{for some} \thinspace \text{s} \in \mathbb{N}, \thinspace \text{and primes} \thinspace \text{q}_1,\text{q}_2,…,\text{q}_\text{s}.$
$\text{Then r = s and the} \thinspace \text{p}_\text{r} \thinspace and \thinspace q_\text{s}\thinspace \text{are the same up to ordering}.$

$\text{Lemma: Let m,n} \in \mathbb{N}. \thinspace \text{If m|n, then m} \leq \text{n}.$

$ \text{Let a,b} \in \mathbb{Z} \thinspace \text{such that b} \neq 0 \thinspace \text{and suppose that}$
$\text{there exists q,r} \in \mathbb{Z^+} \thinspace \text{such that a=bq+r then (a,b)=(b,r)}$

$ d|c_1a_1+...+\text{c}_\text{n}\text{a}_\text{n} \thinspace \text{for} \thinspace \text{c}_1,...,\text{c}_\text{n} \in \mathbb{Z}$

(a,b) = gcd (a,b). That is, (a,b)|a and (a,b)|b

(a,b)=gcd(a,b)

a=b=0

1. 1
2. n

$\text{c} \leq (\text{a},\text{b}) $

(d,nd)=d

c|(a,b)

Yes, because 0 times any integer equals 0.

No, the greatest common divisor (GCD) is always positive because any negative number is less than any positive number.

$\text{Let S be a subset of}\thinspace \mathbb{N}$
$\text{For all n} \in \mathbb{N}, \text{if} \thinspace \text{k} \in \text{S} \thinspace \text{then} \thinspace \forall \text{k} \in \mathbb {N} \thinspace \text{such that k<n}, \thinspace n \in S. \text{Then S = N } $

$\text{Let S be a nonempty subset of} \thinspace \mathbb{N} \thinspace \text{then S has a least element}.$
$\text{That is, there exists an} \thinspace \text{s} \in \text{S} \thinspace \text{such that} \thinspace \text{s} \leq \text{n} \thinspace \text{for all n} \in \text{S}.$

$\left\{ \begin{matrix} \text{p, if p|n} \\ 1, \text{otherwise} \end{matrix} \right\} $

prime or product of primes

$\text{For} \thinspace \text{m},\text{n} \in \mathbb{N}, \text{m}|\text{n} \iff \thinspace \text{each prime in the prime power representation of m} $
$\text{occurs to a power less than or equal to that of which it occurs in n}. $

There are infinitely many primes

$\text{The Euclidean Algorithm is a way to determine (a,b) for any two integers a and b such that} \thinspace \text{a} \neq 0 \thinspace \text{and} \thinspace \text{b} \neq 0.$

$\text{The Extended Euclidean Algorithm is a way to write (a,b) as a linear combination of a and b such that} \thinspace \text{a} \neq 0 \thinspace \text{and} \thinspace \text{b} \neq 0.$

$\bullet \thinspace 1 \in \mathbb{N}$
$\bullet \thinspace \text{For each n} \in \mathbb{N}, \text{there exists a successor}$
$\bullet \thinspace \text{1 is not the successor of any element of}\thinspace \mathbb{N}$
$\bullet \thinspace\text{Any subset S of } \thinspace \mathbb{N} \thinspace \text{such that}$
$-1\in \text{S and} $
$-\forall \text{n} \in \mathbb{N} \thinspace \text{whenever n} \in \text{S, n+1} \in \text{S is} \thinspace \mathbb{N} \thinspace \text{itself}$
$\bullet \thinspace \text{Principle of Mathematical Induction}$

$\bullet \thinspace \text{+ (addition) is commutative and associative}$
$\bullet \thinspace \times \text{(multiplication) distributes over addition}$
$\bullet \thinspace \text{< (less than): transitive (If a<b and b<c, then a<c}$
$\bullet \thinspace \text{Trichotomy: For all a,b} \in \mathbb{N}, \text{exactly one of the following is true.}$
$ \text{1. a<b}$
$\text{2. a=b}$
$\text{3. a>b}$
$\text{For all c} \in \mathbb{N}, \text{if a<b then a+c<b+c and ab<ac.}$
$\text{Note if a}\leq \text{b and b} \leq \text{a, then a=b}$
$\bullet \thinspace \text{Another consequence is that we can “start" induction at any natural number.}$

$\bullet\thinspace\text{Commutative, associate, and distributive over addition}$
$\bullet \thinspace \text{Not commutative or associative over subtraction, but distributive over subtraction}$
$\bullet \thinspace\text{< is transitive and has trichotomy;}$
$ \text{moreover, if a,b,c} \in \mathbb{R} \thinspace \text{and a<b, then a+c<b+c but ac<bc is not necessarily true}$