1
$\begingroup$

Let $a,b,c \in \mathbb{Z}$ such that $a|c$, $b|c$, gcd$(a,b)=1$. Prove that $ab|c$.

My thoughts so far: By the Unique Factorization Theorem, we can rewrite $a$ as $p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ where $p_i$'s are primes that make up $a$. Similarly, we can write $b=q_1^{\beta_1}q_2^{\beta_2}...q_k^{\beta_k}$, but with the restriction that $p_i\neq q_j$, $\forall i,j$. Then, by definition of "$|$," we can say that $a|c$ implies $\exists k \in \mathbb{Z}$ such that $k(p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k})=c$. (Similarly for $b$).

From here I am unsure where to go, but it feels like I am only a lemma away from my conclusion.

$\endgroup$
  • $\begingroup$ As a suggestion, try showing now: If $a \mid bc$, $\gcd(a, b) = 1$, then $a \mid c$. $\endgroup$ – cat Sep 14 '16 at 4:26
3
$\begingroup$

Any time you see $gcd(a,b)=1$, it can often be helpful to think of Bezout's identity. $$ gcd(a,b)=1\Rightarrow \exists \; x,y\in\mathbb{Z}\;s.t\; 1=ax+by $$ Then we can scale to get $$ c=cax+cby $$ And now using that $a\vert c,\;b\vert c \Rightarrow c=ak_1=bk_2$ our identity becomes $$ c=cax+cby=axbk_2+aybk_1\Rightarrow c=ab(k_2x+k_1y) $$

$\endgroup$
  • 1
    $\begingroup$ How did you eliminate $x$ and $y$? $\endgroup$ – Bobson Dugnutt Sep 13 '16 at 20:42
  • 1
    $\begingroup$ I shouldnt have, I'll edit $\endgroup$ – qbert Sep 13 '16 at 20:46
  • $\begingroup$ Then you should swap $k_1$ and $k_2$ in the last line (and you're still missing the $x,y$ in the middle equation). $\endgroup$ – Bobson Dugnutt Sep 13 '16 at 21:00
  • $\begingroup$ fixed. next time I'll just put $k\in \mathbb{Z}$ asap $\endgroup$ – qbert Sep 13 '16 at 21:04
1
$\begingroup$

The idea is right. We can first add that it's not restrictive to assume $a,b,c>0$ (verify it).

Since $a\mid c$, we have $c=ak$; every prime power that divides $b$ must so divide $k$.


Alternatively, write $c=abq+r$, with $0\le r<ab$. Since $a\mid c$, we deduce that $a\mid r$ and, similarly, that $b\mid r$. Suppose $r>0$; then $r$ is a multiple of the lowest common multiple of $a$ and $b$, which is $ab$. Hence $r\ge ab$, a contradiction. Therefore $r=0$.

$\endgroup$
1
$\begingroup$

A quick way of going at it is using Gauss Lemma:

If $a$ and $b$ are coprime ($\gcd(a,b)=1$) then $a|bc\implies a|c$.

Reminder of the proof: By Bézout you have $u,v\in\mathbb{Z}$ such that $ua+vb=1$ and you just multiply by $c$ to see it through.

Now your exercice: $b|c$ so $c=bk$; $a|c$ implies by Gauss Lemma that $a|k$, so $ab|c$.

$\endgroup$
1
$\begingroup$

Since $a\mid c$ and $b\mid c$, we must have $\text{lcm}(a,b)\mid c$. We also have $ab=\gcd(a,b)\text{lcm}(a,b)$ and $\gcd(a,b)=1$, therefore $ab=\text{lcm}(a,b)$ and $ab\mid c$.

$\endgroup$
0
$\begingroup$

Since $a|c$ and $b | c$, there are $j, k$ such that $aj = c$ and $bk = c$.

Subce $gcd(a, b) = 1$, there are $u, v$ such that $au-bv = 1$.

$aju-bjv = j$ and $aku-bkv = k$ or $cu-bjv = j$ and $aku-cv = k$.

Once more, $acu-abjv = aj = c$ and $baku-bcv = bk = c$.

Adding these (because subtracting didn't do it), $2c =c(au-bv)-ab(ku-jv) =c-ab(ku-jv) $ or $c =ab(jv-ku) $ so $ab | c$.

Wadda ya know? I played around for a while and it worked!

$\endgroup$

Your Answer

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