Sunday, September 8, 2019

abstract algebra - How to prove that $zgcd(a,b)=gcd(za,zb)$





I need to prove that $z\gcd(a,b)=\gcd(za,zb)$.




I tried a lot, for example, looking at set of common divisors of the two sides, but I can't conclude anything from that. Can you please give me some advice how I can handle this problem? And $a,b,z \in \mathbb{Z}$.


Answer



Below are a few proofs of the gcd distributive law $\rm\:(ax,bx) = (a,b)x\:$ using Bezout's identity, universal gcd laws, and unique factorization. In each proof the first line serves as a hint.







First we show that the gcd distributive law follows immediately from the fact that, by Bezout, the gcd may be specified by linear equations. Distributivity follows because such linear equations are preserved by scalings. Namely, for naturals $\rm\:a,b,c,x \ne 0$



$\rm\qquad\qquad \phantom{ \iff }\ \ \ \:\! c = (a,b) $



$\rm\qquad\qquad \iff\ \: c\:\ |\ \:a,\:b\ \ \ \ \ \ \&\ \ \ \ c\ =\ na\: +\: kb,\ \ \ $ some $\rm\:n,k\in \mathbb Z$



$\rm\qquad\qquad \iff\ cx\ |\ ax,bx\ \ \ \&\ \ \ cx = nax + kbx,\ \,$ some $\rm\:n,k\in \mathbb Z$



$\rm\qquad\qquad { \iff }\ \ cx = (ax,bx) $




The reader familiar with ideals will note that these equivalences are captured more concisely in the distributive law for ideal multiplication $\rm\:(a,b)(x) = (ax,bx),\:$ when interpreted in a PID or Bezout domain, where the ideal $\rm\:(a,b) = (c)\iff c = gcd(a,b)$






Alternatively, more generally, in any integral domain $\rm\:D\:$ we may employ the universal definitions of GCD, LCM to generalize the above proof.



Theorem $\rm\ \ (a,b)\ =\ (ax,bx)/x\ \ $ if $\rm\ (ax,bx)\ $ exists in $\rm\:D.$



Proof $\rm\quad\: c\ |\ a,b \iff cx\ |\ ax,bx \iff cx\ |\ (ax,bx) \iff c\ |\ (ax,bx)/x\ \ \ $ QED




Such universal definitions often serve to simplify proofs, e.g. see this proof of the GCD * LCM law.






Alternatively, comparing powers of primes in unique factorizations, it reduces to the following
$$ \min(a+c,\,b+c)\ =\ \min(a,b) + c$$



The proof is precisely the same as the prior proof, replacing gcd by min, and divides by $\le$, and




$$\begin{eqnarray} {\rm employing}\quad\ c\le a,b&\iff& c\le \min(a,b)\quad&&\rm[universal\ definition\ of\ \ min]\\
\rm the\ analog\ of\quad\ c\ \, |\, \ a,b&\iff&\rm c\ \ |\ \ gcd(a,b)\quad&&\rm[universal\ definition\ of\ \ gcd] \end{eqnarray}$$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...