Intereting Posts

Limit of $a_n$, where $a_1=-\frac32$ and $3a_{n+1}=2+a_n^3$.
Proof that there can be no planar graph with 5 faces, such that any two of them share an edge.
Why do zeta regularization and path integrals agree on functional determinants?
Sums of binomial coefficients
Borel hierarchy doesn't “collapse” before $\omega_1$
A sufficient condition for differentiability of a function of several variables in terms of differentiability along paths.
Integral $\int_0^\pi \cot(x/2)\sin(nx)\,dx$
point deflecting off of a circle
Proof by induction: $n$th Fibonacci number is at most $ 2^n$
Gosper's Identity $\sum_{k=0}^n{n+k\choose k}=1 $
Proof that$ (a+A)\cap A=\varnothing$ if $A$ is countable
Solve $z^6=(z-1)^6$.
Probability for having consecutive success in an experiment
A quick question on transcendence
Is $\sqrt{5}$ in $\mathbb Q(\sqrt{2})$?

I was reading a text book and came across the following:

Important Results

(This comes immediately after LCM:)If 2 [integers] $a$ and $b$ are given, and their $LCM$ and $HCF$ are $L$ and $H$ respectively,

then $L \times H = a \times b$

- Coprime cofactors of n'th powers are n'th powers, up to associates, for Gaussian integers
- Proving that $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n )} - 1$
- If $\gcd(a,b)=1$ and $a$ and $b$ divide $c$, then so does $ab$
- Divide by a number without dividing.
- Prove by induction $\vphantom{\Large A}3\mid\left(n^{3} - n\right)$
- If $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$

Can some please help me understand why the above result is true?

Thanks in advance.

- Do these arithmetic rules work? They extend the number system by a zero not based on the empty set that is a divisor with unique quotients.
- Prove that $\sum_{d|n}\phi(d)=n$ where $\phi$ is the Euler's phi function, $n,c\in\mathbb{N}$
- How do I compute $a^b\,\bmod c$ by hand?
- Solving $13\alpha \equiv 1 \pmod{210}$
- How to prove: $2^\frac{3}{2}<\pi$ without writing the explicit values of $\sqrt{2}$ and $\pi$
- Can I prove (if $n^2$ is even then $n$ is even) directly?
- Divisibility of coefficients $\binom{n}{k}$ with fixed composite $n$
- Proving $\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$
- Congruence question with divisibility
- Solve $x^2+2=y^3$ using infinite descent?

Let $p$ be a prime. If $p$ occurs in $a$ with multiplicity $m$ and in $b$ with multiplicity $n$, then it will occur in the LCM of $a$ and $b$ with multiplicity $\mathrm{max(m,n)}$ and in their HCF with multiplicity $\mathrm{min(m,n)}$.

Hence, in the product of LCM and HCF the multiplicity of $p$ is $$\mathrm{max}(m,n)+\mathrm{min}(m,n)=m+n,$$

which is also the multiplicity of $p$ in $a\cdot b$. Since this holds for every $p$, the two products must be equal.

Below is a proof that works in any domain, using the universal definitions of GCD, LCM.

**THEOREM** $\rm\quad (a,b)\ =\ ab/[a,b] \;\;$ if $\;\rm\ [a,b] \;$ exists.

**Proof**: $\rm\qquad d\mid (a,b)\iff d\mid a,b \iff a,b\mid ab/d \iff [a,b]\mid ab/d \iff d\mid ab/[a,b] $

You can also figure this out without using any use of unique factorization. Since you say this comes immediately after LCM, I assume you know that for $m\gt 0$, $[ma,mb]=m[a,b]$, where $[a,b]=\mathrm{lcm}(a,b)$ and $(ma,mb)=m(a,b)$ where $\gcd(a,b)=(a,b)$.

Now suppose $(a,b)=1$, and also assume they are positive, since if they are negative $[a,-b]=[a,b]$ anyway. Since $[a,b]$ is some multiple of $a$, let $[a,b]=ma$. Then $b\mid ma$, but $(a,b)=1$, so $b\mid m$. If this hasn’t be addressed yet, notice $(ma,mb)=m(a,b)=m$, so $b\mid ma$, and $b\mid mb$, so $b\mid m$ since any common divisor of $ma$ and $mb$ divides the greatest common divisor $m$ in this case.

So $b\leq m$ as they are both positive, which implies $ba\leq ma$. But $ba$ is a common multiple of $a$ and $b$, so cannot be strictly less than $ma$, so $ba=ma=[a,b]$.

More generally, if $(a,b)=g\gt 1$, then you have $(\frac{a}{g},\frac{b}{g})=1$. Then by the special case above,

$$

\left[\frac{a}{g},\frac{b}{g}\right]\left(\frac{a}{g},\frac{b}{g}\right)=\frac{a}{g}\frac{b}{g}.

$$

Multiply through by $g^2$, you have

$$

\begin{align*}

g^2\left[\frac{a}{g},\frac{b}{g}\right]\left(\frac{a}{g},\frac{b}{g}\right) &= g\left[\frac{a}{g},\frac{b}{g}\right]g\left(\frac{a}{g},\frac{b}{g}\right)\\

&= [a,b](a,b)\\

&= g^2\frac{a}{g}\frac{b}{g}=ab

\end{align*}

$$

so $[a,b](a,b)=|ab|$.

- How can I get the negation of $\exists!$ (unique existential quantification)?
- Mean Value Property of Harmonic Function on a Square
- Is a morphism between schemes of finite type over a field closed if it induces a closed map between varieties?
- Claim: $a$ has $90 \% $ primes less than $n$ If $n!= 2^s \times a \times b $ and $\lfloor{\frac{a}{b}}\rfloor = 2^{s-2}$
- Question on groups of order $pq$
- “Too simple to be true”
- How to solve $\mathrm dX(t)=B(t)X(t)\mathrm dt+B(t)X(t)\mathrm dB(t)$ with condition $X(0)=1$?
- improper integral convergence test
- Why can we always take the zero section of a vector bundle?
- A System of Matrix Equations (2 Riccati, 1 Lyapunov)
- Every group is the quotient of a free group by a normal subgroup
- Convergence of fixed point iteration for polynomial equations
- Discriminant of a binary quadratic form and Jacobi symbol
- Non-standard models of arithmetic for Dummies (2)
- Why $y=e^x$ is not an algebraic curve?