Exercise 1.3.49* (Divisors of $ab, cd$ and $ac+bd$.)

Question

If $g$ is a divisor of each $ab,cd$, and $ac + bd$, prove that it is also a divisor of $ac$ and $bd$, where $a,b,c,d$ are integers.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

Notation: If $p$ is prime and $n$ an integer, $
u_p(n)$ denotes the higher power of $p$ which divides $n$. Therefore, if $k$ is an integer,
$$ k = 
u_p(n) \iff p^k \mid n 	ext{ and } p^{k+1} 
mid n.$$
\begin{proof} Suppose that $g\mid ab, g\mid cd$, and $g \mid ac + bd$, where $g = p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ is the decomposition of $g$ in prime factors.

It is sufficient to prove $p_i^{\alpha_i} \mid ac,\ p_i^{\alpha_i} \mid bd$ for $i=1,\ldots,k$.

\bigskip
Assume that $p^\alpha \mid g$ for some prime $p$ and exponent $\alpha$.

Then
$$p^\alpha \mid ab, \qquad p^\alpha \mid cd,\qquad p^\alpha \mid ac +bd.$$

Define
\begin{align*}
&u = 
u_p(a),\qquad v = 
u_p(b),\
&s = 
u_p(c),\qquad t = 
u_p(d).
\end{align*}
Then there are integers $q_1,q_2,q_3,q_4$ such that
\begin{align*}
&a = p^u q_1,\qquad b = p^v q_2,\qquad p
mid q_1,\ p
mid q_2\
&c = p^s q_3,\qquad d = p^t q_4,\qquad p
mid q_3,\ p
mid q_4.
\end{align*}
Therefore
$$p^\alpha \mid ab = p^{u+v} q, \qquad 	ext{where } p
mid q= q_1q_2.$$
Since $p 
mid q$, where $p$ is prime,  $p^\alpha \wedge q = 1$, thus $p^{\alpha} \mid p^{u+v}$ so
\begin{align}
\alpha \leq u+v.
\end{align}
Similarly, using
$$p^\alpha \mid cd = p^{s+t} r, \qquad 	ext{where } p
mid r=q_3q_4,$$
\begin{align}
\alpha \leq s +t.
\end{align}

Moreover
\begin{align}
&ac = p^{u+s}\, q' \qquad 	ext{where } p 
mid q'= q_1q_3,\
&bd = p^{v+t}\,  r'\qquad 	ext{where } p
mid r'= q_2q_4.
\end{align}
\begin{itemize}
\item If $u+s \leq v+t$, then
\begin{align*}
ac + bd &= p^{u+s}(q' + p^{v+t-u-s} r')\
&= p^{u+s} z,
\end{align*}
where $z = q' + p^{v+t-u-s} r' \in \N$,  and $p 
mid z$.

Since $p^\alpha \mid ac+bd = p^{u+s} z$, and $p \wedge z = 1$,
$\alpha \leq u+s.$

Then (3) implies  $p^\alpha \mid ac$. Since $p^\alpha \mid  ac+bd$, we obtain also $p^\alpha \mid bd$.
\item If $u+s \geq v+t$, then similarly
\begin{align*}
ac + bd &= p^{v+t}(r' +p^{u+s-v-t} q')\
&= p^{v+t} z', 
\end{align*}
where $z' = r' +p^{u+s-v-t} q' \in \N$,  and  $p 
mid z'$.

Since $p^\alpha \mid ac +bd = p^{v+t} z'$, where $p
mid z'$, we obtain $\alpha \leq v+t$.

Then (4) implies $p^\alpha \mid bd$. Since $p^\alpha \mid  ac+bd$, we obtain also $p^\alpha \mid ac$.

\end{itemize}
I both cases, $p^\alpha \mid ac$ and $p^\alpha \mid bd$.

I we apply this result to every $p_i^{\alpha_i}$ for $i = 1,\ldots,k$, we conclude that $p_i^{\alpha_i} \mid ac $ and $p_i^{\alpha_i} \mid bd$. Therefore $g =p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ is a divisor of $ac$ and $bd$.
\end{proof}

Exercise 1.3.49* (Divisors of $ab, cd$ and $ac+bd$.)

Answers

Comments

Exercise 1.3.49* (Divisors of $ab, cd$ and $ac+bd$.)

Answers

Comments

Add answer