$(a^{n},b^{n})=(a,b)^{n}$ and $[a^{n},b^{n}]=[a,b]^{n}$?

Question

How to show that $$(a^{n},b^{n})=(a,b)^{n}$$ and $$[a^{n},b^{n}]=[a,b]^{n}$$ without using modular arithmetic? Seems to have very interesting applications.$$$$Try: $(a^{n},b^{n})=d\Longrightarrow d\mid a^{n}$ and $d\mid b^n$

Answer 1

If $p$ is a prime and $p^t$ is the highest power of $p$ dividing $a$, then $p^{tn}$ is the highest power dividing $a^n$.

Therefore $\text{gcd}(a^n,b^n)=\text{gcd}(a,b)^n$.

For the other one, start with $$ \text{lcm}(a,b)=\frac{ab}{\text{gcd}(a,b)} $$ and take $n$-th powers both sides.

Answer 2

Bezout's Identity says that $\gcd(a,b)$ is the smallest positive element of $\{ax+by:x,y\in\mathbb{Z}\}$.

The smallest positive element of $\{acx+bcy:x,y\in\mathbb{Z}\}$ is $\gcd(ac,bc)$; it is also $c$ times the smallest positive element of $\{ax+by:x,y\in\mathbb{Z}\}$ which is $\gcd(a,b)$. Therefore $$ \gcd(ac,bc)=c\gcd(a,b)\tag{1} $$ Suppose $ax+by=1$ and $au+cv=1$, then $$ \begin{align} by\,cv&=(1-ax)(1-au)\\ &=1-a(x+u-axu)\\ a(x+u-axu)+bc\,vy&=1 \end{align} $$ Thus, $$ \gcd(a,b)=1\quad\text{and}\quad\gcd(a,c)=1\implies\gcd(a,bc)=1\tag{2} $$ Using $(2)$ and induction, we get that $$ \gcd(a,b)=1\implies\gcd\left(a^n,b^n\right)=1\tag{3} $$ Using $(1)$ and $(3)$, we have $$ \begin{align} \gcd(a,b)\gcd\left(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}\right)&=\gcd(a,b)&&(1)\\ \gcd\left(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}\right)&=1&&\text{cancel}\\ \gcd\left(\frac{a^n}{\gcd(a,b)^n},\frac{b^n}{\gcd(a,b)^n}\right)&=1&&(3)\\ \gcd(a,b)^n\gcd\left(\frac{a^n}{\gcd(a,b)^n},\frac{b^n}{\gcd(a,b)^n}\right)&=\gcd(a,b)^n&&\text{multiply}\\[9pt] \gcd\left(a^n,b^n\right)&=\gcd(a,b)^n&&(1)\tag{4} \end{align} $$

---

In this answer, it is shown that $$ \gcd(a,b)\,\mathrm{lcm}(a,b)=ab\tag{5} $$ Therefore, $$ \begin{align} \mathrm{lcm}(a,b)^n &=\frac{(ab)^n}{\gcd(a,b)^n}&&(5)\\ &=\frac{a^n\,b^n}{\gcd(a^n,b^n)}&&(4)\\[4pt] &=\mathrm{lcm}(a^n,b^n)&&(5)\tag{6} \end{align} $$

Answer 3

let gcd(a,b)=d
$\Longrightarrow d|a \wedge d|b$
$\Longrightarrow$ $d|a^n$ $\wedge$ $d|b^n$
$\Longrightarrow$ d|$(a^n,b^n)$---------------(1)

now, $d|(a,b)$ [in fact, $(a,b)=d$]
it implies $d|(a,b)^n$-----------------(2)

by equation (1)and(2), it follows obviously that $(a^n,b^n)=(a,b)^n$

now, it is easy work to derive similar result for lcm by this method.

Answer 4

Show that the common divisors of $a^n$ and $b^n$ all divide $(a,b)^n$ and that any divisor of $(a,b)^n$ divides $a^n$ and $b^n$ (the proofs are pretty straight forward). It might be useful to consider prime factorization for the second direction.

Similarly, show that $[a,b]^n$ is a multiple of $a^n$ and $b^n$ but that it is also the smallest such multiple (and again there, prime factorization might be useful in the second case). If you need more details just ask.

EDIT :

Let's use prime factorization, I think this way everything makes more sense. To show equality, it suffices to show that the prime powers dividing either side are the same. Let's show $(a^n, b^n) = (a,b)^n$ first.

Since $p$ is prime, $p$ divides $a$ if and only if it divides $a^n$ and similarly for $b$ ; so if $p$ does not divide $a$ or $b$, then $p^0 = 1$ is the greatest power of $p$ that divides both sides. If $p$ divides both $a$ and $b$, let $p^k$ be the greatest power of $p$ dividing $(a,b)$, so that $p^{kn}$ is the greatest power of $p$ dividing $(a,b)^n$. Since $p^k$ divides $a$, $p^{kn}$ divides $a^n$, and similarly for $b$. For obvious reasons the greatest power of $p$ dividing both $a^n$ and $b^n$ must be a power of $p^n$. But if $p^{(k+1)n}$ divided both $a^n$ and $b^n$, then $p^{(k+1)}$ would divide $a$ and $b$, contradicting the fact that $p^k$ is the greatest power of $p$ dividing $(a,b)$. Therefore $p^{kn}$ is the greatest power of $p$ dividing $(a^n,b^n)$ and the greatest power of $p$ dividing $(a,b)^n$, so taking the product over all primes, $(a^n,b^n) = (a,b)^n$.

For $[a^n,b^n] = [a,b]^n$ you can do very similar techniques as with the gcd, except all the 'greatest' are replaced by 'smallest' in the last proof, and 'division' is replaced by 'being a multiple of'.

Hope that helps,