Exercise 5.17

Proof.

(a)

Let $b=p_1{p}_2\cdots p_m$, where the $p_i$ are not necessarily distinct primes. For each prime $p_i$, $(a_1,p_i)=(a_2,p_i)$ (Prop. 5.1.2 (c)), so ${\prod <!--\; FUNCTION\; APPLICATION\; -->}_i(a_1,p_i)={\prod }_i(a_2,p_i)$, thus $(a_1∕b)=(a_2∕b)$.

(b)

From Prop. 5.1.2(b),

$(a_1{a}_2∕b)={\prod <!--\; FUNCTION\; APPLICATION\; -->}_i(a_1{a}_2∕p_i)={\prod }_i(a_1∕p_i)(a_2∕p_i)={\prod }_i(a_1∕p_i){\prod }_i(a_2∕p_i)=(a_1∕b)(a_2∕b)$.

(c)

Let $b_1=p_1{p}_2\cdots p_m,b_2=q_1{q}_2\cdots q_l$. Then $b_1{b}_2=p_1{p}_2\cdots p_m{q}_1{q}_2\cdots q_l={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{i=1}^{m+l}{r}_i$, where $r_i=p_i$ for $i=1,\dots ,m$, $r_i=q_{i-m}$ for $i=m+1,\dots ,m+l$. Then

$(a∕b_1{b}_2)={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{i=1}^{m+l}(a∕r_i)={\prod }_{i=1}^m(a∕p_i){\prod }_{j=1}^l(a∕q_i)=(a∕b_1)(a∕b_2)$.

Proof. Let $\mathcal{}P(m)$ the proposition defined by

Then $\mathcal{}P(1)⟺(r_1-1)∕2\equiv (r_1-1)∕2(\mathit{mod}2)$ is true, and $\mathcal{}P(2)$ is part (a) of the lemma. If we make the induction hypothesis $\mathcal{}P(m)$, then

where the last congruence is a consequence of the part (a) of the Lemma : the induction is completed, and $\mathcal{}P(m)$ is true for all $m\ge 1$.

The proof of part (b) is similar. □