5
$\begingroup$

I would like to prove that $\gcd(a,b) = 1$ implies that for any $i,j$ in N, $\gcd(a^{i},b^{i}) = 1$, without using the factorization in prime numbers.

With the factorization it is very easy (you don't have similar factors, and no new factors appear with the power). But without it I'm stuck.

I tried to find a contradiction but nothing came out, supposing that there exists i,j in N such that $\gcd(a,b) = 1$ and $\gcd(a^{i},b^{i}) \ne 1$. Then I have that $a^{i} = k\cdot a'$ and $b^{j} = k\cdot b'$ I could do something to say that $k|a^{n} \Rightarrow k|a$, but I don't see how to prove this without the factorization again.

I also tried induction and proving just that $\gcd(a,b) = 1 \Rightarrow \gcd(a^{2},b) = 1$, but again withtout the factorization it is not clear to me.

Is there any way to do this without the factorization ?

Thanks

$\endgroup$
  • $\begingroup$ Can we use "if $k|ab$ then $k|a$ or $k|b$"? $\endgroup$ – Yanko Sep 20 '18 at 22:03
  • 2
    $\begingroup$ Hint : We have $Aa+Bb=1$, raise this to the power of $2i-1$. $\endgroup$ – Donald Splutterwit Sep 20 '18 at 22:05
  • $\begingroup$ Welcome to MathSE! The part when you write "Then I have that ai=k.a′ bj=k.b′." is confusing. Use a middle dot instead of a lower dot to represent multiplication and I recommend you write at least a word like "and" between those two equalities. $\endgroup$ – evaristegd Sep 20 '18 at 22:06
0
$\begingroup$

Here it is proved that $\gcd(a,b)$ is the smallest positive integer that can be expressed as a linear combination of $a$ and $b$ ($ax + by$, where $x, y \in \mathbb Z$).

A simple corollary would be that, $\gcd(a,b)=1$ if and only if if there exists integers $x$ such that ax+by = 1$.

Next we show that, if $\gcd(a,b) = \gcd(a, c)=1$, then $\gcd(a, bc) = 1$. That $\gcd(a^i,b^j) = 1$ is a consequence of this corollary.

Proof.

If $\gcd(a,b)= 1$, then there exists integers $x$ and $y$ such that $ax+by=1$.

If $\gcd(a,c)= 1$, then there exists integers $u$ and $v$ such that $au+cv=1$. Multiplying, we get

$$a^2xu + acxv+abyu + bcuv = 1$$

Rearranging, we get

$$a(axu+cxv+byu) + bc(uv)=1$$

Which implies $\gcd(a,bc)=1$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.