Assignment 2

Question 1

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

Question 2

Prove that for any integers \(a\), \(b\), \(r\), and \(s\), if \(a \mid b\) and \(a \mid c\), then \(a \mid br + cs\).

Question 3

Prove that if \(a \mid b\) and \(b \mid c\), then \(a \mid c\).

Question 4

Suppose we have arbitrary integers \(\ell\), \(s\), and \(d\) such that \(\ell \mid s\). Prove that \(\ell \mid s + d\) if and only if \(\ell \mid d\).

Question 5

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

Question 6

Disprove: If \(a \mid bc\) then \(a \mid b\) or \(a \mid c\).

Question 7

Disprove: If \(a \mid c\) and \(b \mid c\) then \(ab \mid c\).

Question 8

Prove: If \(a \mid c\) and \(b \mid c\) and \((a, b) = 1\), then \(ab \mid c\).
Hint: \(c = bt\) (Why?), so \(a \mid bt\). Use Theorem 1.4.

Question 9

Use the Euclidean Algorithm to find the greatest common divisor \(d\) of 657 and 306, and express \(d\) as a \(\mathbb{Z}\)-linear combination of 657 and 306.

Question 10

Prove that for any natural number \(n\), \(6 \mid 7^n - 1\).