Chapter 22

* and \(\circ\) are associative.

The set of all the common multiples of \(a\) and \(b\) is an ideal of \(\mathbb{Z}\).

Suppose \(a\) is odd and \(b\) is even, or vice versa. Then \(\operatorname{gcd}(a, b)=\operatorname{gcd}(a+b, a-b)\).

\(\operatorname{gcd}(a, 0)=a\), if \(a>0\)

If \(a \mid b\) and \(b \mid c\), then \(a \mid c\)

Every prime ideal of \(\mathbb{Z}\) is a maximal ideal. [HINT: If \(\langle p\rangle \subseteq\langle a\rangle\), but \(\langle p\rangle \neq\langle a\rangle\), plain why \(\operatorname{gcd}(p, a)=1\) and conclude that \(1 \in\langle a\rangle .]\)

If \(a c \mid b\) and \(a d \mid b\) and \(\operatorname{gcd}(c, d)=1\), then \(a c d \mid b\).

If \(\operatorname{gcd}(a, c)=1\) and \(c \mid a b\), then \(c \mid b\). (Reason as in the proof of Euclid's lemma.)

\(\operatorname{gcd}(a, b)=\operatorname{gcd}(a, b+x a)\) for any \(x \in \mathbb{Z}\)

Let \(d=\operatorname{gcd}(a, b)\). For any integer \(x, d \mid x\) iff \(x\) is a linear combination of \(a\) and \(b\).

If \(a=a_{1} c\) and \(b=b_{1} c\) where \(c=\operatorname{gcd}(a, b)\), then \(\operatorname{lcm}(a, b)=a_{1} b_{1} c\).

Suppose that for all integers \(x, x \mid a\) and \(x \mid b\) iff \(x \mid c\). Then \(c=\operatorname{gcd}(a, b)\).

Suppose every common divisor of \(a\) and \(b\) is a common divisor of \(c\) and \(d\), and ce versa. Then \(\operatorname{gcd}(a, b)=\operatorname{gcd}(c, d)\).

\(a \mid 0\)

\(\operatorname{lcm}(a, a b)=a b\)

Prove by induction: For all \(n>0\), if \(\operatorname{gcd}(a, b)=1\), then \(\operatorname{gcd}\left(a, b^{n}\right)=1\).

Prove by induction: For all \(n>0\), if \(\operatorname{ged}(a, b)=1\), then \(\operatorname{gcd}\left(a, b^{n}\right)=1\).

If \(\operatorname{gcd}(a b, c)=1\), then \(\operatorname{gcd}(a, c)=1\) and \(\operatorname{gcd}(b, c)=1\)

If \(c \mid a\) and \(c \mid b\), then \(c \mid(a x+b y)\) for all \(x, y \in \mathbb{Z}\)

If \(\operatorname{gcd}(a, b)=1\), then \(\operatorname{lcm}(a, b)=a b\).

Suppose \(\operatorname{gcd}(a, b)=1\) and \(c \mid a b\). Then there exist integers \(r\) and \(s\) such that \(c=r s\) \(a, s \mid b\), and \(\operatorname{gcd}(r, s)=1\).

Let \(\operatorname{gcd}(a, b)=c .\) Write \(a=c a^{\prime}\) and \(b=c b^{\prime} .\) Then $$ \operatorname{gcd}\left(a^{\prime}, b^{\prime}\right)=\operatorname{gcd}\left(a, b^{\prime}\right)=\operatorname{gcd}\left(a^{\prime}, b\right)=1 $$

If \(a>0\) and \(b>0\) and \(a \mid b\), then \(a \leq b\).

If \(\operatorname{lcm}(a, b)=a b\), then \(\operatorname{gcd}(a, b)=1\)

If \(\operatorname{gcd}(a, b)=d\), then \(\langle a\rangle+\langle b\rangle=\langle d\rangle .\) (NOTE: If \(J\) and \(K\) are ideals of a ring \(A\) len \(J+K=\\{x+y: x \in J\) and \(y \in K\\} .)\)

Let \(\operatorname{gcd}(a, b)=c\). Then \(\operatorname{lcm}(a, b)=a b / c\),

If \(a \mid b\) and \(c \mid d\), then \(a c \mid b d\).

Let \(\operatorname{gcd}(a, b)=c\) and \(\operatorname{lcm}(a, b)=d .\) Then \(c d=a b\).