Assignment 2

For integers $a$ and $b$ with $b \neq 0$ , state the definition of $b$ divides $a$ .

Prove that for any integers $a$ , $b$ , $r$ , and $s$ , if $a ∣ b$ and $a ∣ c$ , then $a ∣ b r + c s$ .

Prove that if $a ∣ b$ and $b ∣ c$ , then $a ∣ c$ .

Suppose we have arbitrary integers $ℓ$ , $s$ , and $d$ such that $ℓ ∣ s$ . Prove that $ℓ ∣ s + d$ if and only if $ℓ ∣ d$ .

Suppose $a = b q + r$ . Prove the following equality of sets:
\{common divisors of $a$ and $b$ \} = \{common divisors of $b$ and $r$ \}.

Disprove: If $a ∣ b c$ then $a ∣ b$ or $a ∣ c$ .

Disprove: If $a ∣ c$ and $b ∣ c$ then $a b ∣ c$ .

Prove: If $a ∣ c$ and $b ∣ c$ and $(a, b) = 1$ , then $a b ∣ c$ .
Hint: $c = b t$ (Why?), so $a ∣ b t$ . Use Theorem 1.4.

Use the Euclidean Algorithm to find the greatest common divisor $d$ of 657 and 306, and express $d$ as a $Z$ -linear combination of 657 and 306.

Prove that for any natural number $n$ , $6 ∣ 7^{n} - 1$ .